秋招笔试惨痛经历之——动态规划

1. 面试高频

  1. 正则匹配
class Solution {
    public boolean isMatch(String s, String p) {
        /*
        正则表达式匹配
        7.22
        */
        //动态规划

        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];
    }
}
  1. 打家劫舍3问
//线性
class Solution {
    public int rob(int[] nums) {
        /*
        打家劫舍，数组
        7.25
        */
        //动态规划

        //判断空
        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的结果和1比较
            second = Math.max(first+nums[i],second);
            //0替换为1
            first = temp;
        }

        return second;
    }
}


//环形
class Solution {
    public int rob(int[] nums) {
        /*
        打家劫舍，环形
        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
        */
        //偷当前节点和不偷当前节点

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

        //使用数组接收返回结果
        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;
        }

        //左子树递归结果
        int[] left = MyRob(root.left);
        //右子树递归结果
        int[] right = MyRob(root.right);

        //偷当前节点：当前+不能偷左右
        result[0] = root.val + left[1] + right[1];
        //不偷当前：左右最大值
        result[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

        return result;
    }
}
  1. 股票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];
            //当利润大于0时，进行叠加
            if(temp > 0){
                profit += temp;
            }

        }

        return profit;
    }
}

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

        /*
        股票含冷冻期
        7.26
        */
        //使用dp数组表示三种状态
        //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]);
    }
}
  1. 凑硬币(巨经典)
//如果没有给定硬币面额，使用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;
}
  1. 爬楼梯(2步和3步)
//1和2步：f(n) = f(n-1) + f(n-2)
class Solution {
    public int climbStairs(int n) {
        /*
        爬楼梯(台阶)
        7.24
        */
        //递归，使用数组存小结果

        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];
        
        //外层为数量
        for(int i=0;i<num;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]);
    }
}
  1. 0-1背包策略数
    给定N个正整数A1,A2,…,AN，从中选出若干个数，使它们的和为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);

        //每个数只能用一次，且数字顺序不同，结果不相同
        //最大限制：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]);
    }
}
  1. 完全背包
    有 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];
        
        //外层为数量
        for(int i=0;i<nums;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]);
    }
}
  1. 单词拆分
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /*
        单词拆分
        7.25
        */
        //动态规划，使用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区间搜索
            for(int j=0;j<i;j++){
                //如果dp[j]为true且set中含有从j到i的子字符串，将当前dp[i]标记为true，说明wordDict中含有s，break跳出j循环
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
}
  1. 丑数
class Solution {
    public int nthUglyNumber(int n) {
        /*
        丑数，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++){
            //本次丑数：
            int n2 = 2 * dp[a];
            int n3 = 3 * dp[b];
            int n5 = 5 * dp[c];

            //本次最先丑数
            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];
    }
}
  1. 剪绳子(分割整数)
class Solution {
    public int integerBreak(int n) {
        /*
        整数拆分(剪绳子)
        7.26
        */
        //一维dp

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

        //初始化dp数组
        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
        */
        //动态规划，Arrays.sort(envelopes,(a,b) -> (a[0] - b[0]))进行降维

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

        //创建dp数组
        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++){
                //当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;
    }
}
  1. 最大矩形：先初始化，然后从当前行往左搜，提取高和宽
class Solution {
    public int maximalRectangle(char[][] matrix) {

        /*
        8.17，二维动态规划
        */

        //二维dp，可以先初始化dp数组，矩阵中为1，dp[i][j] = dp[i-1][j] + 1。将dp数组第一行设置为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数组，在当前位置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;
    }
}
  1. 编辑距离
class Solution {
    public int minDistance(String word1, String word2) {
        /*
        8.17，二维dp
        */

        //dp数组，行为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++){
                //当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()];
    }   
}
  1. 不同路径(有无障碍)
//无障碍
class Solution {
    public int uniquePaths(int m, int n) {
        /*
        不同路径，无障碍
        7.24
        */
        //动态规划，初始化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要用来判断是否要终止路径

        //可以创建dp数组，初始化dp数组的第一行和第一列来进行叠加
        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];
    }
}
  1. 最大正方形
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;
    }
}
  1. 三角形最小路径和：自底向上
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        三角形最小路径和
        7.25
        */
        //二维dp，自底向上

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

        //往上搜索，当前行 + 下一行的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];
    }
}
  1. 最小路径和
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){
                    //第一行，左 + 当前
                    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.min(grid[i-1][j],grid[i][j-1]) + grid[i][j];
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
  1. 最大路径和
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];
}
  1. 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;
}
  1. 大疆笔试：0-1背包
    有许多程序员都热爱玩游戏，而小J自称为游戏王，曾玩过几百种游戏，几乎所有能玩到的游戏大作都玩遍了。随着时间的推移，他发觉已经没有游戏可以让他玩了！于是他想改玩一些古老的游戏，以成为真正的“游戏王”。他希望在接下来的一段时间内将过去出的游戏全部玩一遍，但是毕竟时间有限，因此他感到很苦恼。于是他想到一个计划，他先将每个游戏标上一个成就值，同时对每个游戏都估算一个通关所需要的天数，他计划在未来X天内让自己玩游戏的成就达到最大，那么他应该怎么做计划呢？（假设每个游戏最多只计划玩一遍，而且每个游戏必须玩完通关才能取得成就值，且通关每个游戏最小时间单位是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);
 
        //数量
        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背包，从后往前遍历，外层遍历为数量，内层遍历为限制条件
        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]);
    }
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容