区块链技术博客
www.b2bchain.cn

算法-动态规划

这篇文章主要介绍了算法-动态规划,通过具体代码讲解6042并且分析了算法-动态规划的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了算法-动态规划。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6042。具体如下:

算法 动态规划

算法

发布日期:   2019-12-04
文章字数:   5.3k
阅读时长:   23 分
阅读次数:  

序列型dp就是序列+状态,直接看几个例子。

1、LintCode 515 Paint House

【问题】这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小,返回最小的费用。费用通过一个nx3 的矩阵给出,比如cost[0][0]表示房屋0染红色的费用,cost[1][2]表示房屋1染绿色的费用。

【分析】典型的序列型动态规划,序列型动态规划 = 序列+状态。确定状态,一共三种

  • 如果最优策略中,最后一栋是红色,那么倒数第二栋只能是蓝色或绿色
  • 如果最优策略中,最后一栋是蓝色,那么倒数第二栋只能是红色或绿色
  • 如果最优策略中,最后一栋是绿色,那么倒数第二栋只能是蓝色或红色

那么需要分别记录倒数第二栋房子是红色、蓝色、绿色的最小花费即可,只要最后一栋和倒数第二栋颜色不一样。

初始条件:序列型dp需要开n+1行,每列表示一种状态,dp[0][0] = dp[0][1] = dp[0][2] = 0,第0栋房子花费是0。

public int minCost(int[][] costs) {         if (costs.length == 0) {             return 0;         }         int rows = costs.length;         //序列型动态规划,一共三种颜色,一共要rows栋房子,另外加一个第0栋存放初始值         int[][] dp = new int[rows + 1][3];         //初始化第0栋         dp[0][0] = dp[0][1] = dp[0][2] = 0;          //i是第i栋房子         for (int i = 1; i < dp.length; i++) {             //第i栋房子要染成3种颜色种的哪一种             for (int j = 0; j < 3; j++) {                 dp[i][j] = Integer.MAX_VALUE;                 //前i-1栋房子的颜色                 for (int k = 0; k < 3; k++) {                     if (j != k) {                         dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i-1][j]);                     }                 }             }         }         return Math.min(dp[rows][0], Math.min(dp[rows][1], dp[rows][2]));     }

2、LintCode 516 Paint House II

【问题】这里有n个房子在一列直线上,现在我们需要给房屋染色,共有k种颜色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小。费用通过一个nxk 的矩阵给出,比如cost[0][0]表示房屋0染颜色0的费用,cost[1][2]表示房屋1染颜色2的费用。

【分析】原来是三种颜色,现在变成k种颜色

第一种写法,直接把刚才的3改成现在的k,时间复杂度O(NK^2^)

public static int minCostII(int[][] costs) {         if (costs == null || costs.length == 0 || costs[0].length == 0) {             return 0;         }         int n = costs.length;         int m = costs[0].length;         int[][] dp = new int[n + 1][m];     //序列型         dp[0][0] = 0;   //第0栋耗费为0          //从第一栋房子开始         for (int i = 1; i <= n; i++) {             //第一栋房子的三种颜色             for (int j = 0; j < m; j++) {                 dp[i][j] = Integer.MAX_VALUE;                 //前一栋房子                 for (int k = 0; k < m; k++) {                     if (j != k) {                         dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + costs[i - 1][j]);                     }                 }             }         }         int min = Integer.MAX_VALUE;         for (int i = 0; i < dp[0].length; i++) {             if (dp[n][i] < min) {                 min = dp[n][i];             }         }         return min;     }

优化:上面的思路每次需要求f[i-1][1], ..., f[i-1][K]中除了一个元素之外,其他元素的最小值。这里解决思路是保存最小值和次小值,首先把f[i-1][1], ..., f[i-1][K]中的最小值和次小值先记录下来。

  • 如果除掉的元素不是最小值,那剩下的最小值就是最小值它本身
  • 如果除掉的元素是最小值,那剩下的元素中,最小值就是次小值

假设i-1栋房子,最小值是f[i-1][a],次小值是f[i-1][b],如果第i栋染颜色a,那么最小花费就是加上次小值,否则就是加上最小值。

时间复杂度O(NK)

public static int minCostII(int[][] costs) {         if (costs == null || costs.length == 0 || costs[0].length == 0) {             return 0;         }         int n = costs.length;       //房屋数         int m = costs[0].length;    //颜色个数         int[][] dp = new int[n + 1][m];         for (int i = 0; i < dp[0].length; i++) {    //初始化第一行,第0栋             dp[0][i] = 0;         }         int min1, min2; //min1存放最小值,min2存放次小值         int id1 = 0;   //id1存放最小值的颜色下标,id2存放次小值的颜色下标         int id2 = 0;          for (int i = 1; i <= n; i++) {             min1 = min2 = Integer.MAX_VALUE;             //第i-1栋房子的最小花费和次小花费             for (int j = 0; j < m; j++) {                 //如果当前值比最小值还小,就把最小值先传递给次小值,再更新最小值,其次还要更新id                 if (dp[i - 1][j] < min1) {                     min2 = min1;                     id2 = id1;                     min1 = dp[i - 1][j];                     id1 = j;                 }                 //如果当前值比次小值小,但比最小值大,只需要更新次小值                 else {                     if (dp[i - 1][j] < min2) {                         min2 = dp[i - 1][j];                         id2 = j;                     }                 }             }             for (int j = 0; j < m; j++) {                 //如果和i-1栋颜色不一样,那就直接加最小值,否则加次小值                 if (j != id1) {                     dp[i][j] += min1 + costs[i - 1][j];                 } else {                     dp[i][j] += min2 + costs[i - 1][j];                 }             }         }         int res = Integer.MAX_VALUE;         for (int j = 0; j < dp[0].length; j++) {             if (res > dp[n][j]) {                 res = dp[n][j];             }         }         return res;     }

3、LintCode 392 House Robber

【问题】假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警。给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,在不触动报警装置的情况下, 你最多可以得到多少钱 。

简而言之,不能偷相邻两家,求最多能偷多少金币。

【分析】从最后一步出发,最后一栋房子i是偷还是不偷

  • 偷i,结果 = 第i栋的金币数 + 前i-2(包括i-2)栋偷得的总额
  • 不偷i,结果 = 前 i-1(包括i-1) 栋房子的最优策略

两个状态,用0表示不偷,用1表示偷

  • 第i栋不偷,i-1可偷可不偷,dp[i][0] = max{dp[i-1][0], dp[i-1][1]}
  • 第i栋选择偷,i-1不能偷,dp[i][1] = dp[i-1][0] + A[i-1]
//一般写法 public static long houseRobber(int[] A) {         int n = A.length;         long[][] dp = new long[n + 1][2];         //初始化第0栋房屋         dp[0][0] = dp[0][1] = 0;          for (int i = 1; i <= n; i++) {             //不偷             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);             //偷             dp[i][1] = dp[i - 1][0] + A[i - 1];         }         return Math.max(dp[n][0], dp[n][1]);     }

简化:偷i栋房子时,i-1肯定不能偷,直接去问前i-2栋一功能偷多少,不偷i栋时,问前i-1栋能偷多少

  • dp[i] = max{dp[i-1], dp[i-2] + A[i-1]}
public static long houseRobber(int[] A) {         int n = A.length;         if (n == 0) {             return 0;         }          if (n == 1) {             return A[0];         }         long[] dp = new long[n + 1];         dp[0] = 0;  //前0栋房子,0         dp[1] = A[0];         for (int i = 2; i <= n; i++) {             dp[i] = Math.max(dp[i - 2] + A[i - 1], dp[i - 1]);         }         return dp[n];     }

使用滚动数组优化

public static long houseRobber2(int[] A) {         int n = A.length;         if (n == 0) {             return 0;         }          if (n == 1) {             return A[0];         }         long old = 0;   //dp[0]         long now = A[0];    //dp[1]         for (int i = 2; i <= n; i++) {             long t = Math.max(old + A[i - 1], now);             old = now;             now = t;         }         return now;     }

4、LintCode 534 House Robber II

【问题】上一题是一排房子,现在是一圈房子,然后不能偷任何挨着的两家,求最多能偷多少金币。

【分析】现在第一栋房子和最后一栋房子成了邻居,首尾不能同时偷,就有两种情况:①偷第一栋,最后一栋不能偷,②偷最后一栋,第一栋不能偷。所以只要分别计算去头和去尾两种情况,取一个最大值即可。

public static int houseRobber2(int[] nums) {         int n = nums.length;         if (n == 0) {             return 0;         }         if (n == 1) {             return nums[0];         }          int[] A = new int[n - 1];         long res = Integer.MIN_VALUE;         for (int i = 0; i < n - 1; i++) {             A[i] = nums[i];     //去尾的情况         }         res = Math.max(res, calc(A));          for (int i = 0; i < n - 1; i++) {             A[i] = nums[i+1];       //去头的情况         }         res = Math.max(res, calc(A));         return (int) res;     }      public static long calc(int[] A) {         int n = A.length;         if (n == 0) {             return 0;         }          if (n == 1) {             return A[0];         }         long old = 0;   //dp[0]         long now = A[0];    //dp[1]         for (int i = 2; i <= n; i++) {             //now = dp[i-1],old = dp[i-2]             long t = Math.max(old + A[i - 1], now);             old = now;             now = t;         }         return now;     }

5、LintCode 149 买卖股票的最佳时机I

【问题】假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

【分析】维护到当前位置i的最小值,利润 = 当天卖出价格 - 最小值价格,更新res数组

public int maxProfit(int[] prices) {         int n = prices.length;         if (n == 0 || n < 2) {             return 0;         }          int minVal = prices[0];         int res = 0;         for (int i = 0; i < n; i++) {             minVal = Math.min(minVal, prices[i]);             res = Math.max(res, prices[i] - minVal);         }         return res;     }

6、LintCode 149 买卖股票的最佳时机II

【问题】给定一个数组 prices 表示一支股票每天的价格.你可以完成任意次数的交易, 不过你不能同时参与多个交易 (也就是说, 如果你已经持有这支股票, 在再次购买之前, 你必须先卖掉它).设计一个算法求出最大的利润。

简而言之:I中只能买卖一次,现在可以买卖任意多次,任何时刻最多持有一股,求获得的最大利润。

【分析】贪心,只要今天价格比昨天价格高,就卖掉,这里贪心就是最优的,因为抓住了每一个上升段
算法-动态规划

public int maxProfit(int[] prices) {         int n = prices.length;         if (n < 2) {             return 0;         }         int res = 0;         for (int i = 1; i < n; i++) {             if (prices[i] - prices[i - 1] > 0) {        //只要比昨天价格高,就卖掉                 res += prices[i] - prices[i - 1];             }         }         return res;     }

7、LintCode 151 买卖股票的最佳时机III——序列型

【问题】假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

限定交易次数为2次,不能手里同时有两支股票,可以同一天卖完后买入

【分析】需要记录已经买卖多少次。最后一步就是最后一次卖掉,发生在第j天,需要枚举最后一次买是在第几天,但不知道之前有没有买卖过,所以需要记录状态,一共五种状态如下所示
算法-动态规划

  • 阶段1、3、5手里虽然没股票,但是境界不一样,分别是买卖过0次、1次、2次
  • 阶段2、4是持有股票阶段,可以选择持有股票或卖出
  • 最优策略必定处于阶段1、3、5,不可能处于2、4,买了不卖,那就亏了。所以需要求在阶段1、阶段3、阶段5时三种清仓状态下的最大获利分别是多少。

【状态转移方程】

  • dp[i][j]表示前i天(第i-1)天结束后,在阶段j的最大获利
  • 阶段1、3、5,无股票状态,两种可能:昨天无股票并保持无股票状态 或 昨天有股票今天卖出
    • dp[i][j] = max{dp[i-1][j],dp[i-1][j-1] + prices[i-1] - prices[i-2]}
  • 阶段2、4,手里持有股票,两种可能:昨天有股票并保持有股票状态(获利和亏损都有可能,要加上) 或 昨天没股票今天买入
    • dp[i][j] = max{dp[i-1][j] + prices[i-1] - prices[i-2],dp[i-1][j-1]}

【初始化与边界】

  • dp[0][1] = 0;dp[0][2] = ... = dp[0][5] = Integer.MIN_VAULE
  • 注意几个边界
  • 最多买卖两次,必定在清仓状态下获利最多
public int maxProfit(int[] prices) {         int n = prices.length;         int[][] dp = new int[n + 1][5 + 1];          //初始化         dp[0][1] = 0;         for (int i = 2; i <= 5; i++) {             dp[0][i] = Integer.MIN_VALUE;         }          //遍历n天的价格         for (int i = 1; i <= n; i++) {              //阶段1、3、5,手里不持有股票             for (int j = 1; j <= 5; j += 2) {                 dp[i][j] = dp[i - 1][j];                 //肯定是第一个阶段以后的,所以j>1,且上一个阶段dp[i - 1][j - 1]不能为无穷小                 if (i - 2 >= 0 && j > 1 && dp[i - 1][j - 1] != Integer.MIN_VALUE) {                     //继续不持有,或者昨天持有,今天卖掉变为不持有                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i - 1] - prices[i - 2]);                 }             }              //阶段2、4,手里持有股票             for (int j = 2; j <= 4; j += 2) {                 //从上一个不持有的阶段变为持有                 dp[i][j] = dp[i - 1][j - 1];                 //不用判断j,从阶段2开始,且昨天持有时dp[i - 1][j]不能为无穷小                 if (i - 2 >= 0 && dp[i - 1][j] != Integer.MIN_VALUE) {                     //继续持有,继续获利,或是今天才买入                     dp[i][j] = Math.max(dp[i - 1][j] + prices[i - 1] - prices[i - 2], dp[i - 1][j - 1]);                 }             }         }         return Math.max(dp[n][1], Math.max(dp[n][3], dp[n][5]));     }

8、LintCode 393 买卖股票的最佳时机IV

【问题】在买卖股票的最佳时机III的中,买卖次数为2次,在这里变为K次买卖。

【分析】原来2次买卖股票,分为5个阶段,现在K次买卖,就分成了2K+1次

  • 阶段1、3、5...2K+1都是没有持有股票的阶段
  • 阶段2、4、6...2K都是持有股票的阶段

这样就能直接套买卖股票III中的模版了,但是解题时发现超时,因为当K > N/2时,直接退化为任意次买卖股票了,需要特殊考虑,解题代码如下

public int maxProfit(int K, int[] prices) {         int n = prices.length;         if (K > n / 2) {             int res = 0;             for (int i = 1; i < n; i++) {                 if (prices[i] - prices[i - 1] > 0) {                     res += prices[i] - prices[i - 1];                 }             }             return res;         } else {             int[][] dp = new int[n + 1][2 * K + 1 + 1];             //初始化             dp[0][1] = 0;             for (int i = 2; i <= 2 * K + 1; i++) {                 dp[0][i] = Integer.MIN_VALUE;             }              for (int i = 1; i <= n; i++) {                  //阶段1、3、5...2K+1,不持有股票                 for (int j = 1; j <= 2 * K + 1; j += 2) {                     //初始是继续保持不持有的状态                     dp[i][j] = dp[i - 1][j];                     if (i >= 2 && j > 1 && dp[i - 1][j - 1] != Integer.MIN_VALUE) {                         //保持不持有的状态或是昨天有股票,今天卖出                         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i - 1] - prices[i - 2]);                     }                 }                 //阶段2、4、6...2K,持有股票的阶段                 for (int j = 2; j <= 2 * K; j += 2) {                     //初始是从不持有的阶段过来                     dp[i][j] = dp[i - 1][j - 1];                     if (i >= 2 && dp[i - 1][j] != Integer.MIN_VALUE) {                         //继续保持持有阶段并获利,或是昨天没有,今天买入                         dp[i][j] = Math.max(dp[i - 1][j] + prices[i - 1] - prices[i - 2], dp[i - 1][j - 1]);                     }                 }             }             int res = Integer.MIN_VALUE;             for (int i = 1; i <= 2 * K + 1; i += 2) {                 res = Math.max(res, dp[n][i]);             }             return res;         }     }

9、LintCode 76 最长上升子序列

【问题】给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。这里可以不连续,因为是子序列,不是子串。

【分析】假设最长上升子序列是以a[j]结尾的,那么子序列中倒数第二个元素必定比a[j]小

  • 很容易得出f[j] = max{1, f[i] + 1 | i < j && a[i] < a[j]},答案是其中的最大值

写出如下代码,这里我试着打印子序列的路径,时间复杂度为O(N^2^)

public static int longestIncreasingSubsequence(int[] nums) {         int n = nums.length;         if (n == 0) {             return 0;         }         int[] dp = new int[n];         int[] path = new int[n];    //记录路径         int end = -1;         int res = Integer.MIN_VALUE;         for (int i = 0; i < n; i++) {             dp[i] = 1;             path[i] = -1;   //初始路径为-1             for (int j = 0; j < i; j++) {                 if (nums[j] < nums[i]) {                     dp[i] = Math.max(dp[i], dp[j] + 1);                     //如果第i个个来自j处,那就更新                     if (dp[i] == dp[j] + 1) {                         path[i] = j;                     }                 }             }             res = Math.max(res, dp[i]);             //记下来是在哪结束的             if (res == dp[i]) {                 end = i;             }         }          int[] temp = new int[res];         for (int i = 0; i < temp.length; i++) {             temp[i] = nums[end];             end = path[end];         }         for (int i = temp.length - 1; i >= 0; i--) {             System.out.print(temp[i] + " ");         }         return res;     }

优化:时间复杂度为O(nlogn)

/**      * 优化成O(N logN),看到这个就只有二分法了      * 优化:一旦前面有两个dp值一样了,比如dp[i] = dp[j],并缺nums[i] > nums[j] ,那就只要考虑第j个就可以了      * 也就是 同样的dp值,存一个坐标,这个坐标对应的nums[index]值最小。那么对于每个dp值,保存一下对应的nums[i]的值      * 序列是单调上升的,在单调上升中找最后一个比自己小的数用二分法      * 我们开个数组,数组的下表为dp值,对应存的是该dp值下最小的nums[idx]      */      //1、使用 binarySearch()     public static int longestIncreasingSubsequence(int[] nums) {         if (nums == null || nums.length == 0) {             return 0;         }         int n = nums.length;         int[] a = new int[n];         int res = 0;         for (int i = 0; i < nums.length; i++) {             //在a数组的这个区间内找有没有nums[i],如果key在数组中,则返回搜索值的索引;否则返回-1或“-”(插入点)。插入点是索引键将要插入数组的那一点             int index = Arrays.binarySearch(a, 0, res, nums[i]);             //如果如果这个数比之前的数大,就找不到插入位置,它就会在新位置插入,如果这个数比之前的数小,就会直接覆盖之前的数             if (index < 0) {                 index = -index - 1;             }             //把这个数放在插入点上             a[index] = nums[i];             if (index == res) {                 res++;             }         }         return res;     }      /**      * 使用TreeSet      * TreeSet基本操作全是log(n)复杂度(欢迎纠正),时间复杂度也一致。      * TreeSet.ceiling(x)方法可以直接找出set中大于x的最小数字,如果不存在则返回null。      *      * 1. 如果这个数字存在,则删除这个数字,然后把x插入set中,相当于代替该数字。      * 2. 如果这个数字不存在,说明x大于set中任何数字,直接把x插入set中。      * 最后返回set的大小即可。      */      public int longestIncreasingSubsequence(int[] nums) {         TreeSet<Integer> set = new TreeSet<>();         for (int num : nums) {             Integer ceiling = set.ceiling(num);             //如果set中大于num的最小数字存在,删除这个数字,放入num             if (ceiling != null) {                 set.remove(ceiling);             }             set.add(num);         }         return set.size();     }

10、LintCode 602 俄罗斯套娃信封

【问题】给一定数量的信封,带有整数对 (w, h) 分别代表信封宽度和高度。一个信封的宽高均大于另一个信封时可以放下另一个信封。求最多嵌套多少个信封。

【分析】这个属于最长序列型dp,dp都是从最后一步出发,先考虑最后一步,也就是最后一个信封Ei,然后考虑次外层信封,一定是某个Ej,并且Ej里面嵌套的信封也是最多的。得出

  • dp[i] = max{1,dp[j] + 1}(①只能这一个信封,②Ej能放进Ei中)dp[i]表示以信封Ei为最外层信封时,最多嵌套层数。

由于有宽和高两个维度,我们选择一个维度,比如选择宽度,先按照以宽度升序排序

下面算法是正常思路,但时间复杂度为O(N^2^),在Lintcode上通过不了,必须要O(nlogn),但在Leetcode上能通过。

public int maxEnvelopes(int[][] envelopes) {          if (envelopes == null || envelopes.length == 0) {             return 0;         }          //首先对信封按长度进行升序排序,如果长度一样则按照宽度进行升序排序 /*        Arrays.sort(envelopes, new Comparator<int[]>() {             @Override             public int compare(int[] o1, int[] o2) {                 int res = o1[0] - o2[0];                     if (res == 0) {                     return o1[1] - o2[1];                 } else {                     return res;                 }             }         });*/           //直接用lamda表达式         Arrays.sort(envelopes, Comparator.comparing((int[] a) -> a[0]).thenComparing((int[] a) -> a[1]));         int n = envelopes.length;         int[] dp = new int[n];         int res = Integer.MIN_VALUE;         for (int i = 0; i < n; i++) {             //初始化,别忘记             dp[i] = 1;             //i前面所有的信封             for (int j = 0; 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);                 }             }             res = Math.max(res, dp[i]);         }         return res;     }

使用二分优化,原理和最长上升序列一样

//使用二分     public int maxEnvelopes2(int[][] envelopes) {         if (envelopes == null || envelopes.length == 0 || envelopes[0] == null || envelopes[0].length != 2) {             return 0;         }         // 先按 w 升序排序,再按 h 降序 排序!!         // 然后只需考虑h即可,因为w已经升序排列好,因为h大的在前,所以相同的w下的不同h,只会选择最大的那个h,来看以这个h结尾的最长上升子序列         // 当w相同的情况下,h高的在前面,也就是说同样w中是不可能满足increasing subsequence的序列存在,所以任何的increasing subsequence的w一定都是升序的         // 就可以将问题转换为 h 的 Longest Increasing subSequence         Arrays.sort(envelopes, Comparator.comparing((int[] a) -> a[0]).thenComparing((int[] a) -> a[1], Comparator.reverseOrder()));          int dp[] = new int[envelopes.length];         int len = 0;         for (int[] a : envelopes) {             int index = Arrays.binarySearch(dp, 0, len, a[1]);             if (index < 0) {                 index = -index - 1;             }             dp[index] = a[1];             if (index == len) {                 len++;             }         }         return len;     }


算法 动态规划

动态规划:区间型背景:给定一个序列或字符串要进行一些操作,最后一步要将序列或字符串去头、去尾,区间[i,j]变为区间[i+1,j-1],力扣上面的最长回文子串就是这样子操作。区间型dp一般用dp[i] [j],i代表左端点,j代表右端点,若
2019-12-10 算法
动态规划:背包型数组开n+1,背包关键就是看最后一步。 1、01背包–求maxLintCode 92: Backpack 【问题】在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i] 【分析】从最后一
2019-12-02 算法

本文地址https://www.b2bchain.cn/?p=6042

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 算法-动态规划
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们