1. 面試高頻

1. 正則匹配

class Solution {
    public boolean isMatch(String s, String p) {
        /*
        正則表達式匹配
        7.22
        */
        //動態(tài)規(guī)劃

        char[] str = s.toCharArray();
        char[] pstr = p.toCharArray();

        int len1 = str.length;
        int len2 = pstr.length;

        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[len1][len2] = true;

        for(int i=len1;i>=0;i--){
            for(int j=len2-1;j>=0;j--){
                boolean cur = i<len1 && (str[i]==pstr[j] || pstr[j]=='.');

                if(j+1 < len2 && pstr[j+1]=='*'){
                    dp[i][j] = dp[i][j+2] || cur && dp[i+1][j];
                }else{
                    dp[i][j] = cur && dp[i+1][j+1];
                }
            }
        }

        return dp[0][0];
    }
}

2. 打家劫舍3問

//線性
class Solution {
    public int rob(int[] nums) {
        /*
        打家劫舍，數(shù)組
        7.25
        */
        //動態(tài)規(guī)劃

        //判斷空
        if(nums.length == 0){
            return 0;
        }

        //如果只有1個元素，返回第一個元素
        if(nums.length == 1){
            return nums[0];
        }

        //提取first和second
        int first = nums[0];
        int second = Math.max(nums[0],nums[1]);

        //因為不能偷相鄰的，從2開始遍歷
        for(int i=2;i<nums.length;i++){
            //提取second
            int temp = second;
            //0+2的結(jié)果和1比較
            second = Math.max(first+nums[i],second);
            //0替換為1
            first = temp;
        }

        return second;
    }
}


//環(huán)形
class Solution {
    public int rob(int[] nums) {
        /*
        打家劫舍，環(huán)形
        7.26
        */
        //計算偷第一間(0,len-1)和不偷第一間(1,len)的max

        //判斷空
        if(nums.length == 0){
            return 0;
        }

        //如果只有一個元素，返回第一個元素
        if(nums.length == 1){
            return nums[0];
        }

        //如果只有兩個元素，返回其中大的
        if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }

        //偷與不偷
        int[] left = Arrays.copyOfRange(nums,0,nums.length-1);
        int[] right = Arrays.copyOfRange(nums,1,nums.length);

        return Math.max(MyRob(left),MyRob(right));
    }

    public int MyRob(int[] nums){

        int first = nums[0];
        int second = Math.max(nums[0],nums[1]);

        for(int i=2;i<nums.length;i++){

            int temp = second;
            
            second = Math.max(first+nums[i],second);

            first = temp;
        }

        return second;
    }
}


//樹形
class Solution {

    public int rob(TreeNode root) {
        /*
        打家劫舍，樹形
        7.26
        */
        //偷當(dāng)前節(jié)點和不偷當(dāng)前節(jié)點

        //判斷空
        if(root == null){
            return 0;
        }

        //使用數(shù)組接收返回結(jié)果
        int[] result = MyRob(root);

        return Math.max(result[0],result[1]);
    }

    public int[] MyRob(TreeNode root){
        
        int[] result = new int[2];

        //遞歸出口  
        if(root == null){
            return result;
        }

        //左子樹遞歸結(jié)果
        int[] left = MyRob(root.left);
        //右子樹遞歸結(jié)果
        int[] right = MyRob(root.right);

        //偷當(dāng)前節(jié)點：當(dāng)前+不能偷左右
        result[0] = root.val + left[1] + right[1];
        //不偷當(dāng)前：左右最大值
        result[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

        return result;
    }
}

3. 股票3問

//一次交易，直接貪心
class Solution {
    public int maxProfit(int[] prices) {
        /*
        買賣股票的最佳時機，一次購買
        7.25
        */
        //只能買一次，貪心遍歷找到cost最小但prices最大

        int cost = prices[0];
        int result = 0;

        for(int i=1;i<prices.length;i++){
            cost = Math.min(cost,prices[i]);
            result = Math.max(prices[i]-cost,result);
        }

        return result;
    }
}


//多次交易，貪心疊加，大于0就疊加
class Solution {
    public int maxProfit(int[] prices) {
        /*
        股票，多次購買
        7.25
        */
        //貪心

        int profit = 0;

        for(int i=1;i<prices.length;i++){

            int temp = prices[i] - prices[i-1];
            //當(dāng)利潤大于0時，進行疊加
            if(temp > 0){
                profit += temp;
            }

        }

        return profit;
    }
}

//交易冷凍期
class Solution {
    public int maxProfit(int[] prices) {

        /*
        股票含冷凍期
        7.26
        */
        //使用dp數(shù)組表示三種狀態(tài)
        //dp[i][0]表示不持股，初始化為0，可以由前一天是不持股和前一天冷凍期得到
        //dp[i][1]表示持股，初始化為-prices[0]，可以由前一天不持股和前一天持股得到
        //dp[i][2]表示冷凍期，初始化為0，可以由前一天持股得到
        //比較不持股和冷凍期
        
        if(prices.length == 0){
            return 0;
        }

        int[][] dp = new int[prices.length][3];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        //從1開始遍歷
        for(int i=1;i<prices.length;i++){

            //不持股，由前一日不持股和前一日是冷凍期
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);

            //持股，前一日持股和前一日不持股
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);

            //冷凍期，前一日持股
            dp[i][2] = dp[i-1][1]+prices[i];
        }

        return Math.max(dp[prices.length-1][0],dp[prices.length-1][2]);
    }
}

4. 湊硬幣(巨經(jīng)典)

//如果沒有給定硬幣面額，使用dp
class Solution {
    public int coinChange(int[] coins, int amount) {
        /*
        零錢兌換
        7.26
        */
        //一維dp

        //判斷空
        if(coins.length == 0){
            return 0;
        }

        int[] dp = new int[amount+1];
        for(int i=1;i<=amount;i++){
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(i-coins[j] >= 0 && dp[i-coins[j]] != Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }

        if(dp[amount] == Integer.MAX_VALUE){
            return -1;
        }else{
            return dp[amount];
        }
    }
}


//如果給定硬幣面額，如：1，4，16，64。直接從大到小貪心遞減
public int GetCoinCount(int N) {
    N = 1024 - N;
    int count = 0;
    while (N > 0) {
        if (N >= 64) {
            N -= 64;
        } else if (N >= 16) {
            N -= 16;
        } else if (N >= 4) {
            N -= 4;
        } else {
            N--;
        }
        //先從大的面額開始減，減完一次就+1
        count++;
    }
    return count;
}

5. 爬樓梯(2步和3步)

//1和2步：f(n) = f(n-1) + f(n-2)
class Solution {
    public int climbStairs(int n) {
        /*
        爬樓梯(臺階)
        7.24
        */
        //遞歸，使用數(shù)組存小結(jié)果

        int[] result = new int[n+2];
        result[1] = 1;
        result[2] = 2;

        //從3開始
        for(int i=3;i<=n;i++){
            result[i] = result[i-1] + result[i-2];
        }

        return result[n];
    }
}

//貪心爬樓梯：f(n) = 2f(n-1)
public class Solution {
    public int JumpFloorII(int target) {
        
        int sum = 1;
        for(int i=1;i<target;i++){
            sum = 2 * sum;
        }
        return sum;
    }
}

//三步爬樓梯
class Solution {
    public int waysToStep(int n) {
        /*
        三步爬樓梯
        8.25
        */

        int[] result = new int[n+3];
        result[1] = 1;
        result[2] = 2;
        result[3] = 4;

        for(int i=4;i<=n;i++){
            //取余操作
            result[i] = ((result[i-1] + result[i-2]) % 1000000007 + result[i-3]) % 1000000007;
        }

        return result[n];
    }
}

2. 一維dp：背包問題

1. 0-1背包
   有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用。
   第 i 種物品的體積是 vi，價值是 wi。
   求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

import java.util.*;

public class Main{
    public static void main(String[] args){
        //典型的背包問題描述。有最大限制量：背包容量。
        //每樣物品只能用一次。0-1背包。
        //輸入兩列，分別代表不同值
        Scanner sc = new Scanner(System.in);
        
        int nums = sc.nextInt();
        
        int bag = sc.nextInt();
        
        int[] weights = new int[nums];
        int[] values = new int[nums];
        
        for(int i=0;i<nums;i++){
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        
        int[] dp = new int[bag+1];
        
        //外層為數(shù)量
        for(int i=0;i<num;i++){
            //內(nèi)存為限制量，從尾到頭遍歷
            for(int j=bag;j>=weight[i];j--){
                dp[j] = Math.max(dp[j],dp[j-weight[i]] + value[i]);
            }
        }
        System.out.println(dp[bag]);
    }
}

2. 0-1背包策略數(shù)
   給定N個正整數(shù)A1,A2,…,AN，從中選出若干個數(shù)，使它們的和為M，求有多少種選擇方案。

4 4
1 1 2 2

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        //每個數(shù)只能用一次，且數(shù)字順序不同，結(jié)果不相同
        //最大限制：sum值

        int num = sc.nextInt();
        
        int sum = sc.nextInt();
        
        int[] nums = new int[num];
        for(int i=0;i<num;i++){
            nums[i] = sc.nextInt();
        }
        
        int[] dp = new int[sum+1];
        //初始化dp[0]
        dp[0] = 1;
        
        for(int i=0;i<num;i++){
            //0-1背包，從尾往前遍歷
            for(int j=sum;j>=nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        
        System.out.println(dp[sum]);
    }
}

3. 完全背包
   有 N 種物品和一個容量是 V 的背包，每種物品都有無限件可用。
   第 i 種物品的體積是 vi，價值是 wi。
   求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
   輸出最大價值。

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        //背包問題，有最大限制量：背包容量
        //每樣物品可以用無限次，完全背包
        //兩列輸入，分別代表不同值

        int nums = sc.nextInt();
        
        int bag = sc.nextInt();
        
        int[] weights = new int[nums];
        int[] values = new int[nums];
        
        for(int i=0;i<nums;i++){
            weights[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }
        
        int[] dp = new int[bag+1];
        
        //外層為數(shù)量
        for(int i=0;i<nums;i++){
            //內(nèi)存為限制量，從頭到尾遍歷
            for(int j=weights[i];j<=bag;j++){
                dp[j] = Math.max(dp[j],dp[j-weights[i]] + values[i]);
            }
        }
        
        System.out.println(dp[bag]);
    }
}

4. 單詞拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /*
        單詞拆分
        7.25
        */
        //動態(tài)規(guī)劃，使用hashset去重wordDict

        //將wordDict傳入set進行去重
        Set<String> set = new HashSet<>(wordDict);

        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;

        //一維dp
        for(int i=1;i<=s.length();i++){

            //i到j(luò)區(qū)間搜索
            for(int j=0;j<i;j++){
                //如果dp[j]為true且set中含有從j到i的子字符串，將當(dāng)前dp[i]標記為true，說明wordDict中含有s，break跳出j循環(huán)
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}

5. 丑數(shù)

class Solution {
    public int nthUglyNumber(int n) {
        /*
        丑數(shù)，dp
        8.17
        */

        int a = 0;
        int b = 0;
        int c = 0;

        int[] dp = new int[n+1];
        dp[0] = 1;

        for(int i=1;i<=n;i++){
            //本次丑數(shù)：
            int n2 = 2 * dp[a];
            int n3 = 3 * dp[b];
            int n5 = 5 * dp[c];

            //本次最先丑數(shù)
            dp[i] = Math.min(n2,Math.min(n3,n5));

            if(n2 == dp[i]){
                a++;
            }
            if(n3 == dp[i]){
                b++;
            }
            if(n5 == dp[i]){
                c++;
            }
        }

        return dp[n-1];
    }
}

6. 剪繩子(分割整數(shù))

class Solution {
    public int integerBreak(int n) {
        /*
        整數(shù)拆分(剪繩子)
        7.26
        */
        //一維dp

        //長度小于2時，返回n
        if(n < 2){
            return 0;
        }

        //初始化dp數(shù)組
        int[] dp = new int[n+1];
        dp[2] = 1;

        for(int i=3;i<=n;i++){
            for(int j=0;j<i;j++){
                dp[i] = Math.max(dp[i],Math.max((i-j)*j,dp[i-j]*j));
            }
        }

        return dp[n];
    }
}

3. 二維dp：

1. 俄羅斯套娃：降維成一維的最長上升子序列

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        /*
        俄羅斯套娃，最長上升子序列的二維版本，可以通過Arrays.sort()進行降維
        8.15
        */
        //動態(tài)規(guī)劃，Arrays.sort(envelopes,(a,b) -> (a[0] - b[0]))進行降維

        if(envelopes.length == 0 || envelopes[0].length == 0){
            return 0;
        }

        //創(chuàng)建dp數(shù)組
        int[] dp = new int[envelopes.length];
        //初始化為1
        Arrays.fill(dp,1);

        //降維
        Arrays.sort(envelopes,(a,b) ->(a[0] - b[0]));

        int result = 0;
        //一維dp做法
        for(int i=0;i<envelopes.length;i++){
            for(int j=0;j<i;j++){
                //當(dāng)i的第一和第二個元素都比j的大時
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }

            //本次i遍歷的result
            result = Math.max(result,dp[i]);
        }

        return result;
    }
}

2. 最大矩形：先初始化，然后從當(dāng)前行往左搜，提取高和寬

class Solution {
    public int maximalRectangle(char[][] matrix) {

        /*
        8.17，二維動態(tài)規(guī)劃
        */

        //二維dp，可以先初始化dp數(shù)組，矩陣中為1，dp[i][j] = dp[i-1][j] + 1。將dp數(shù)組第一行設(shè)置為1，疊加high
        if(matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }

        int[][] dp = new int[matrix.length][matrix[0].length];

        //初始化dp
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                if(matrix[i][j] == '1'){
                    if(i == 0){
                        //初始化第一行為1
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = dp[i-1][j] + 1;
                    }
                }
            }
        }

        int result = 0;
        //遍歷dp數(shù)組，在當(dāng)前位置dp[i][j]往左搜寬的最大值
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                if(dp[i][j] == 0){
                    continue;
                }

                int curHigh = dp[i][j];
                //從j往左搜，計算寬，因為是同一行搜，min維持high不變，
                for(int k=j;k>=0 && dp[i][k] != 0;k--){
                    //min維持high是i這一層
                    curHigh = Math.min(curHigh,dp[i][k]);
                    int width = j - k + 1;
                    result = Math.max(result,curHigh*width);
                }
            }
        }

        return result;
    }
}

3. 編輯距離

class Solution {
    public int minDistance(String word1, String word2) {
        /*
        8.17，二維dp
        */

        //dp數(shù)組，行為word1，列為word2，保留[0,0]
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        //word1為空，word1要進行word2.length次添加操作，初始化第一行
        for(int i=1;i<=word2.length();i++){
            dp[0][i] = dp[0][i-1] + 1;
        }

        //word2為空，word1要進行word1.length次刪除操作，初始化第一列
        for(int i=1;i<=word1.length();i++){
            dp[i][0] = dp[i-1][0] + 1;
        }

        //從[1,1]開始填表
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                //當(dāng)word1.charAt(i-1) == word2.charAt(j-1)時，dp[i][j] = dp[i-1][j-1]
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }   
}

4. 不同路徑(有無障礙)

//無障礙
class Solution {
    public int uniquePaths(int m, int n) {
        /*
        不同路徑，無障礙
        7.24
        */
        //動態(tài)規(guī)劃，初始化dp為1，疊加上和左即可得到路徑

        //判斷空
        if(m == 0 || n == 0){
            return 0;
        }

        //m為列，n為行
        int[][] dp = new int[n][m];

        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                //如果i==0，是上邊界，置為1，
                if(i == 0){
                    dp[i][j] = 1;
                }else if(j == 0){
                    //j==0，是左邊界，置為1
                    dp[i][j] = 1;
                }else{
                    //左+上
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[n-1][m-1];
    }
}

//有障礙
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /*
        8.17，二維dp，路徑類型
        */

        //無法在二維矩陣中直接進行疊加，因為矩陣中的1要用來判斷是否要終止路徑

        //可以創(chuàng)建dp數(shù)組，初始化dp數(shù)組的第一行和第一列來進行疊加
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];

        for(int i=0;i<obstacleGrid[0].length;i++){
            if(obstacleGrid[0][i] == 1){
                dp[0][i] = 0;
                break;
            }else{
                dp[0][i] = 1;
            }
        }

        for(int i=0;i<obstacleGrid.length;i++){
            if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
                break;
            }else{
                dp[i][0] = 1;
            }
        }

        //從[1,1]開始疊加
        for(int i=1;i<obstacleGrid.length;i++){
            for(int j=1;j<obstacleGrid[0].length;j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

        return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

5. 最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        /*
        最大正方形
        7.26
        */
        //二維dp，

        //判斷空
        if(matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }

        int[][] dp = new int[matrix.length][matrix[0].length];

        int side = 0;
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                if(matrix[i][j] == '1'){
                    //初始化第一行和第一列
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;

                    }else{
                        //左，左上，上的min + 1
                        dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
                    }

                    //計算邊長
                    side = Math.max(dp[i][j],side);
                }
            }
        }

        return side*side;
    }
}

6. 三角形最小路徑和：自底向上

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        三角形最小路徑和
        7.25
        */
        //二維dp，自底向上

        int len = triangle.size();
        int[][] dp = new int[len+1][len+1];

        //往上搜索，當(dāng)前行 + 下一行的min
        for(int i=len-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }

        return dp[0][0];
    }
}

7. 最小路徑和

class Solution {
    public int minPathSum(int[][] grid) {
        /*
        最小路徑和
        7.23
        */
        //二維dp，疊加原矩陣，求和

        //判斷空
        if(grid.length == 0 || grid[0].length == 0){
            return 0;
        }

        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                //如果i==0且j==0，左上角，continue
                if(i==0 && j==0){
                    continue;
                }else if(i == 0){
                    //第一行，左 + 當(dāng)前
                    grid[i][j] = grid[i][j-1] + grid[i][j];
                }else if(j == 0){
                    //第一列，上 + 當(dāng)前
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                }else{
                    grid[i][j] = Math.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

8. 最大路徑和

class Solution {
    public int maxValue(int[][] grid) {
        /*
        禮物的最大價值(最大路徑和)
        7.27
        */
        //二維dp，可直接疊加原矩陣

        if(grid.length == 0 || grid[0].length == 0){
            return 0;
        }

        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i == 0 && j == 0){
                    continue;
                }else if(i == 0){
                    //上邊界，左疊加
                    grid[i][j] = grid[i][j-1] + grid[i][j];
                }else if(j == 0){
                    //左邊界，上疊加
                    grid[i][j] = grid[i-1][j] + grid[i][j];
                }else{
                    grid[i][j] = Math.max(grid[i-1][j],grid[i][j-1]) + grid[i][j];
                }
            }
        }

        return grid[grid.length-1][grid[0].length-1];
    }
}

4. 筆試原題

1. 奇安信筆試：湊硬幣(3步)

public static int CalulateMethodCount (int num_money) {
    // write code here
 
    int[] result = new int[num_money + 3];
    result[1] = 1;
    result[2] = 2;
    result[3] = 4;
    for (int i = 4; i <= num_money; i++) {
        result[i] = result[i - 1] + result[i - 2] + result[i - 3];
    }
 
    return result[num_money];
}

2. B站筆試：湊硬幣(2步)，給定了硬幣面額，直接貪心從大到小遞減。硬幣面額：1，4，16，64.

public int GetCoinCount(int N) {
    N = 1024 - N;
    int count = 0;
    while (N > 0) {
        if (N >= 64) {
            N -= 64;
        } else if (N >= 16) {
            N -= 16;
        } else if (N >= 4) {
            N -= 4;
        } else {
            N--;
        }
        //先從大的面額開始減，減完一次就+1
        count++;
    }
    return count;
}

3. 大疆筆試：0-1背包
   有許多程序員都熱愛玩游戲，而小J自稱為游戲王，曾玩過幾百種游戲，幾乎所有能玩到的游戲大作都玩遍了。隨著時間的推移，他發(fā)覺已經(jīng)沒有游戲可以讓他玩了！于是他想改玩一些古老的游戲，以成為真正的“游戲王”。他希望在接下來的一段時間內(nèi)將過去出的游戲全部玩一遍，但是畢竟時間有限，因此他感到很苦惱。于是他想到一個計劃，他先將每個游戲標上一個成就值，同時對每個游戲都估算一個通關(guān)所需要的天數(shù)，他計劃在未來X天內(nèi)讓自己玩游戲的成就達到最大，那么他應(yīng)該怎么做計劃呢？（假設(shè)每個游戲最多只計劃玩一遍，而且每個游戲必須玩完通關(guān)才能取得成就值，且通關(guān)每個游戲最小時間單位是1天）

樣例輸入
2 2
10 1
20 2
樣例輸出
20
提示
輸入樣例二:
3 4
10 2
18 3
10 2
輸出樣例二:
20

// 有限制條件，求最值，兩組輸入，游戲只能玩一次——0-1背包
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        //有限制條件時間，兩組輸入求最值，背包問題
        //每個游戲只能玩一次，0-1背包
 
        Scanner sc = new Scanner(System.in);
 
        //數(shù)量
        int num = sc.nextInt();
        //限制條件：時間
        int time = sc.nextInt();
 
        //成就值
        int[] values = new int[num];
        //花費時間
        int[] times = new int[num];
        for(int i=0;i<num;i++){
            values[i] = sc.nextInt();
            times[i] = sc.nextInt();
        }
 
        //背包
        int[] dp = new int[time+1];
 
        //0-1背包，從后往前遍歷，外層遍歷為數(shù)量，內(nèi)層遍歷為限制條件
        for(int i=0;i<num;i++){
            for(int j=time;j>=times[i];j--){
                dp[j] = Math.max(dp[j],dp[j-times[i]] + values[i]);
            }
        }
 
        System.out.println(dp[time]);
    }
}