目录动态规划的三个特征动态规划解题思路1.状态转移表法2. 状态转移方程法3. LeetCode题解3.1 LeetCode 509. 斐波那契数3.2 LeetCode 70. 爬楼梯3.3 LeetCode 198. 打家劫舍3.4 LeetCode 53. 最大子序和3.5 LeetCode 152. 乘积最大子数组3.6 LeetCode 1014. 最佳观光组合3.7 LeetCode 55. 跳跃游戏动态规划适合解决多阶段决策最优解模型问题动态规划的三个特征1.最优子结构2.无后效性3.重复子问题动态规划解题思路1.状态转移表法回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表0-1背包问题我们有一个背包背包总的承载重量是Wkg。现在我们有n个物品每个物品的重量不等并且不可分割。我们现在期望选择几件物品装载到背包中。在不超过背包所能装载重量的前提下如何让背包中物品的总重量最大我们用一个二维数组states[n][w1]来记录n个物品放入载重w公斤背包的状态。第0个下标从0开始编号物品的重量是2要么装入背包要么不装入背包决策完之后会对应背包的两种状态背包中物品的总重量是0或者2。我们用states[0][0]true和states[0][2]true来表示这两种状态。第1个物品的重量也是2基于之前的背包状态在这个物品决策完之后不同的状态有3个背包中物品总重量分别是0(00)2(02 or 20)4(22)。我们用states[1][0]truestates[1][2]truestates[1][4]true来表示这三种状态。以此类推直到考察完所有的物品后整个states状态数组就都计算好了。我把整个计算的过程画了出来你可以看看。图中0表示false1表示true。我们只需要在最后一层找一个值为true的最接近w这里是9的值就是背包中物品总重量的最大值。根据上面的状态转移表推导出递推关系写出动态规划代码weight:物品重量n:物品个数w:背包可承载重量 public int knapsack(int[] weight, int n, int w) { boolean[][] states new boolean[n][w1]; // 默认值false states[0][0] true; // 第一行的数据要特殊处理可以利用哨兵优化 if (weight[0] w) { states[0][weight[0]] true; } for (int i 1; i n; i) { // 动态规划状态转移 for (int j 0; j w; j) {// 不把第i个物品放入背包 if (states[i-1][j] true) states[i][j] states[i-1][j]; } for (int j 0; j w-weight[i]; j) {//把第i个物品放入背包 if (states[i-1][j]true) states[i][jweight[i]] true; } } for (int i w; i 0; --i) { // 输出结果 if (states[n-1][i] true) return i; } return 0; }2.状态转移方程法找最优子结构-写状态转移方程-将状态转移方程翻译成代码3. LeetCode题解3.1 LeetCode509. 斐波那契数例如斐波那契数列数列我们可以很容易知道他的状态转移方程是 f(n)f(n-1)f(n-2)。递归的实现如下int fib(int n) { if(n1) return n; return fib(n-1)fib(n-2); }由于计算f(n)需要先计算f(n-1)和f(n-2)但计算f(n-1)又需要计算f(n-2)和f(n-3);计算f(n-2)需要计算f(n-3)和f(n-4)。这个递归推导计算中有大量重复计算时间复杂度是O(n!)。重复子问题正是动态规划要解决的重复子问题很适合用动态规划解决。动态规划实现int fib(int n) { if(n1) return n; vectorint dp(n1); dp[0] 0; dp[1] 1; for(int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }此实现使用了动态规划问题最优解包含了子问题的最优解最优子结构每一步计算都只依赖上一步无后效性没有重复计算解决重复子问题。这个算法的时间复杂度是O(n)不过空间复杂度也是O(n)。一般动态规划问题都可以写出一个O(n)大小的状态转移方程不过大部分问题都可以转换为O(1)的空间因为我们只需要上一步的状态和当前的状态。int fib(int n) { if(n1) return n; int a1 0, a2 1; int res 0; for(int i 2; i n; i) { res a1a2; a1 a2; a2 res; } return res; }上面这个算法使用动态规划实现了O(n)的时间复杂度空间复杂度O(1)。3.2 LeetCode 70. 爬楼梯int climbStairs(int n) { if(n2) return n; int a1 1, a2 2; int res 0; for(int i 3; i n; i) { res a1a2; a1 a2; a2 res; } return res; }归纳总结后发现状态转移方程也是f(n) f(n-1)f(n-2)只是要注意初始状态f(1)1,f(2)23.3 LeetCode 198. 打家劫舍int rob(vectorint nums) { if(nums.size() 1) return nums[0]; if(nums.size() 2) return max(nums[0], nums[1]); int a1 nums[0]; int a2 max(nums[0], nums[1]); int an 0; for (int i 2; i nums.size(); i) { an max(a1nums[i],a2); a1 a2; a2 an; } return an; }状态转移方程 f(n) max(f(n-2)num[n], f(n-1))3.4 LeetCode 53. 最大子序和int maxSubArray(vectorint nums) { int maxCur nums[0], maxRes nums[0]; for (int i 1; i nums.size(); i) { maxCur max(maxCurnums[i], nums[i]); maxRes max(maxRes, maxCur); } return maxRes; }状态转移方程 f(n) max(f(n-1)num[i], num[i]);3.5 LeetCode 152. 乘积最大子数组int maxProduct(vectorint nums) { int maxCur nums[0]; int minCur nums[0]; int maxRes nums[0]; for(int i 1; i nums.size(); i){ int mx maxCur, mn minCur; maxCur max(mx*nums[i], max(nums[i], mn*nums[i])); minCur min(mn*nums[i], min(nums[i], mx*nums[i])); maxRes max(maxCur, maxRes); } return maxRes; }3.6 LeetCode 1014. 最佳观光组合int maxScoreSightseeingPair(vectorint values) { int maxSum values[0], maxRes 0; for (int i 1; i values.size(); i) { maxRes max(maxRes, maxSumvalues[i]-i); maxSum max(maxSum, values[i]i); } return maxRes; }3.7 LeetCode 55. 跳跃游戏bool canJump(vectorint nums) { if(nums.size()1) return true; int maxIndex{}; for (int i 0; i nums.size()-1;i) { maxIndex max(maxIndex, inums[i]); if(maxIndex i1) return false; } return true; }状态转移方程 f(n) max(f(n), inum[i]);