数据结构与算法学习⑥(动态规划

动态规划1、初识动态规划1.1、从贪心说起1.1.1、贪心的特点1.1.2、贪心的局限性1.1.3、贪心失效后怎么办1.1.4、从最优化问题到递归 1.2、记忆化递归（备忘录）1.2.1、朴素递归的弊端1.2.2、如何剪枝与优化1.2.3、总结 1.3、动态规划解决硬币找零1.3.1、动归问题的特征1.3.2、什么是最优子结构？1.3.3、状态转移方程1.3.4、状态缓存与循环1.3.5、求解零钱兑换1.3.6、通用的动态规划1.3.7子序列系列300. 最长上升子序列 2、动态规划题目1143. 最长公共子序列72. 编辑距离5. 最长回文子串516. 最长回文子序列 题目(背包和打家劫舍系列)背包系列1、0-1背包1.1、问题描述1.2、算法分析和实现 2、416. 分割等和子集2.1、解法分析2.2、状态压缩 3、518. 零钱兑换 II打家劫舍系列198. 打家劫舍

动态规划

1、初识动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

核心观点是: 通过以递归的方式将其分解为更简单的子问题来简化复杂的问题,如果可以通过将问题分解为子问题然后递归地找到子问题的最优解来最佳地解决问题，则可以说它具有最优子结构。

动态规划一般用于去解决最优化系列的问题

1.1、从贪心说起

1.1.1、贪心的特点

所谓贪心算法，就是指它的每一步计算作出的都是在当前看起来最好的选择，也就是说它所作出的选择只是在某种意义上的局部最优选择，并不从整体最优考虑。在这里把这两种选择的思路称作局部最优解和整体最优解。

像之前讲到的：322. 零钱兑换

贪心的思路就是每次都用最大的面额，然后用次大的，…

class Solution {//贪心思路:每次都找局部最优解 public int coinChange(int[] coins, int amount) {//定义组合总数 int count = 0; Arrays.sort(coins); for (int i=coins.length-1;i>=0;i--) {//计算该面额能用几次 int currentCount = amount / coins[i]; if (currentCount==0) {continue; }//该面额用完后剩余的面额 amount = amount % (currentCount * coins[i]) ; //统计所用硬币个数 count+= currentCount; if (amount ==0) {return count; } }return -1;}}

1.1.2、贪心的局限性

从零钱兑换的例子中可以看出，如果coins=[10,9,1],amount=18，贪心算法并不能得到最终的最优解，

这就是贪心算法所谓的局部最优导致的问题，因为我们每一步都尽量多地使用面值最大的硬币，因为这样数量肯定最小，但是有的时候我们就进入了死胡同，就好比上面这个例子。

所谓局部最优，就是只考虑“当前”的最大利益，既不向前多看一步，也不向后多看一步，导致每次

都只用当前阶段的最优解。那么如果纯粹采用这种策略我们就永远无法达到整体最优，也就无法求得题目的答案了。

虽然纯粹的贪心算法作用有限，但是这种求解局部最优的思路在方向上肯定是对的，毕竟所谓的整体最优肯定是从很多个局部最优中选择出来的，因此所有最优化问题的基础都是贪心算法。

1.1.3、贪心失效后怎么办

在硬币找零问题中，当贪心失效后我们在贪心的基础上加入了失败后的回溯，稍微牺牲一点当前利益，仅仅是希望通过下一个硬币面值的局部最优达到最终可行的整体最优。

class Solution {public void sort (int[] coins) {//为了方便先Arrays.sort,然后倒置 Arrays.sort(coins); int n = coins.length-1; int temp; for (int i=0;i<=(n-1)/2;i++) {temp = coins[i];coins[i] = coins[n-i]; coins[n-i] = temp;} }public int coinChange(int[] coins, int amount) {//对coins从大到小排序 sort(coins); dfs(coins,amount,0,0); if (minCount == Integer.MAX_VALUE) {return -1; }return minCount; }//全局最优解使用的最少硬币数量 int minCount = Integer.MAX_VALUE; public void dfs (int[] coins,int amount,int selectedCount,int startIndex) {//如果amount==0则终止 if (amount==0) {if (selectedCount < minCount) {minCount = selectedCount; }return; }if (startIndex >= coins.length) {return; }//计算当前硬币最多能使用多少次 int maxCount = amount / coins[startIndex];//从选择列表[0,maxCount]中选择,然后递归到下一个硬币 for (int i=maxCount;i>=0 && i+selectedCount < minCount ;i--) {//选择i个该硬币后剩余的额度 int resAmount = amount - i*coins[startIndex]; //drill down dfs(coins,resAmount,selectedCount+i,startIndex+1); }} }

整体的思路是：穷举所有组合情况，过程中仍然每次找最大的以期望更快找到最优解，并且通过剪枝减少穷举次数，最终在所有满足条件的组合中找到最优解.

所有贪心的思路就是我们最优化求解的根本思想，所有的方法只不过是针对贪心思路的改进和优化而已。回溯(递归)解决的是正确性问题，而动态规划则是解决时间复杂度的问题。

1.1.4、从最优化问题到递归

为什么最优化问题跟递归有关系?两个方面

1: 在求解最优化问题的时候，我们经常会用到回溯这个策略。在硬币找零这个问题里，具体说就是如果遇到已经无法求解的组合，那么我们就往回退一步，修改上一个面值的硬币数量，然后再尝试新的组合。递归这种形式，正是赋予了回溯这种可以回退一步的能力：它通过堆栈保存了上一步的当前状态。因此，如果想要用回溯的策略来解决问题，那么递归应该是你的首选方法。所以说，回溯在最优化问题中有多么重要，递归也就有多么重要。

2: 枚举与递归, 最优组合的求解策略,如果想得到最优组合，那么最简单直接的方法肯定就是枚举。枚举就是直接求出所有满足条件的组合，然后看看这些组合是否能得到最大值或者最小值。

枚举本身很简单，就是把所有组合都遍历一遍即可。问题就是如何得到这些组合呢？这就需要我们通过一些策略来生成所有满足条件的组合, 而递归正是得到这些组合的方法。最优化问题使用递归来处理是非常清晰的，递归是搜索组合的一种非常直观的思路。

比如:322. 零钱兑换,直接递归枚举搜索所有组合

1、是否有重复子问题：能够兑换成功其实就是amount变化到0的过程，中间的每一个过程我们都是在coins中选择硬币来完成，所以具备重复性

2、递推公式如何表示

f(x)= min( f(x-c) +1 ),x>0,f(x-c)!=-1,x代表amount值,c代表coins中的硬币金额 其中f(0)=0, 如果x<0则f(x) =-1;

class Solution {public int coinChange(int[] coins, int amount) {return dfs(coins,amount); }//返回当前面额amount需要使用的硬币个数 public int dfs(int[] coins,int amount) {//terminal if (amount==0) {return 0; }//定义面额组合成功所需的最少硬币数量int minCount = Integer.MAX_VALUE; for (int i=0;i<coins.length;i++) {//当前硬币面额大于剩余额度,当前硬币不可用 if (coins[i] > amount ) {continue; }//使用一次当前硬币,再接着选 int rearCount = dfs(coins,amount-coins[i]);//返回后面组合的硬币数量 if (rearCount ==-1 ) {//说明这种组合不可行,跳过 continue; }//组合可行,记录当前组合使用的硬币数量int currentCount = rearCount + 1; if (currentCount < minCount) {minCount = currentCount; } }//如果都没有可用的组合 if (minCount == Integer.MAX_VALUE) {return -1; }return minCount; } }

当然,提交未AC,原因是超时!

当然这跟递归过程中出现的一些问题有关系,我们现在的递归属于朴素递归,说白了就是暴力递归.

1.2、记忆化递归（备忘录）

1.2.1、朴素递归的弊端

1、代码的可读性和可调试性差

虽然递归在数学意义上非常直观，但是如果问题过于复杂，画递归状态树的时候，如果分支极多，那么很多人就很难继续在脑海中模拟出整个求解过程了，当然，我们并不推荐用人肉递归的方式在脑海中模拟整个过程。

另外，一旦程序出现 bug，当你想尝试去调试的时候，就会发现这样的代码几乎没有调试的可能性，而且这种问题在数据规模很大的情况下尤为明显。

2、性能低下

使用递归穷举所有组合结果一般性能很低下，时间复杂度有时候能达到指数级别，如果数据量特别大带来的性能问题就是灾难级别的。

而导致递归性能暴跌的一般主要原因是因为在递归的过程中会产生大量的重复计算，也就是一个问题存在重叠子问题。

比如对于：322. 零钱兑换就存在重叠子问题，该题目画出的递归状态树如下

我们发现其中的F(1),F(2),F(3)均被计算了很多次，另外对于F(4)所在的子树，他们的中间求解过程是完全一样的，我们称之为重叠子问题。

还比如之前作过的一道：剑指 Offer 10- I. 斐波那契数列

按照朴素的递归解法

class Solution {public int fib(int n) {//终止条件 if (n < 2) {return n; }else {return fib(n-1) % 1000000007 + fib(n-2) % 1000000007; } }}

如果我们画出其递归的状态树，如下：

我们也能发现，这其中不仅有很多重复计算，更是有很多的重叠子问题。

其实动态规划的核心思想就是通过先解决子问题的最优解来推导原问题的最优解

那如何优化朴素的递归呢？

1.2.2、如何剪枝与优化

1、剪枝

把一些明显不符合最终结果的分支提前剪掉，分支数量减少了，递归的效率自然就高了，这就是所谓的剪枝优化。这个一般通过在递归过程中添加判断条件来实现。

2、参考贪心

递归过程中可以仿照贪心，从整个搜索策略上来调整，先考虑最优解的情况，如果不行再找次优解。

比如322. 零钱兑换中我们在递归搜索所有解的过程中每次都先找面额最大的，并且每次都选最大数量，如果递归搜索不匹配，回溯后我们再减少数量再进行搜索。

3、记忆化递归（备忘录）

由于递归的性质决定了它本身是自顶向下（自上而下）的，也就是一个大问题被逐层分解成子问题，直到终止的子问题，然后随着子问题的不断解决最终使得原问题得到解决。在逐层递归的过程中可能会产生一些重复的分支，也就是前面讲的重复计算和重叠子问题。

为了消除重叠子问题，即消灭重复计算的过程。我们可以创建一个备忘录（memorization）（即缓存），在每次计算出某个子问题的答案后，将这个临时的中间结果记录到备忘录里，然后再返回。

接着，每当遇到一个子问题时，我们不是按照原有的思路开始对子问题进行递归求解，而是先去这个备忘录中查询一下。如果发现之前已经解决过这个子问题了，那么就直接把答案取出来复用，没有必要再递归下去耗时的计算了。

对于备忘录，你可以考虑使用以下两种数据结构：

1、数组（Array），通常对于简单的问题来说，使用一维数组就足够了。在后续的课程中，也许要用到更为复杂的状态存储过程，届时要使用更高维度（二维甚至三维）的数组来存储状态。

2、哈希表（Hash table），如果存储的状态不能直接通过索引找到需要的值（比如斐波那契数列问题，你就可以直接通过数组的索引确定其对应子问题的解是否存在，如果存在你就拿出来直接使用），比如你使用了更高级的数据结构而非简单的数字索引，那么你还可以考虑使用哈希表，即字典来存储中间状态，来避免重复计算的问题。

使用记忆化递归来优化322. 零钱兑换朴素递归的代码如下

class Solution {public int coinChange(int[] coins, int amount) {//有[0,amount]共amount+1个子问题,其中amount[0]=0; int[] memo = new int[amount+1]; Arrays.fill(memo,-2);//如果存的是-1代表组合不可用 return dfs(coins,amount,memo); }//返回当前面额amount需要使用的硬币个数public int dfs(int[] coins,int amount,int[] memo) {//先从缓存中拿子问题的解if (memo[amount] != -2) {return memo[amount]; }//terminal if (amount==0) {memo[amount]=0; return 0; }//定义面额组合成功所需的最少硬币数量 int minCount = Integer.MAX_VALUE; for (int i=0;i<coins.length;i++) {//当前硬币面额大于剩余额度,当前硬币不可用 if (coins[i] > amount ) {continue; }//使用一次当前硬币,再接着选 int rearCount = dfs(coins,amount-coins[i],memo);//返回后面组合的硬 币数量 if (rearCount ==-1 ) {//说明这种组合不可行,跳过continue; }//组合可行,记录当前组合使用的硬币数量 int currentCount = rearCount + 1; if (currentCount < minCount) {minCount = currentCount;}}//如果都没有可用的组合 if (minCount == Integer.MAX_VALUE) {memo[amount] = -1; return -1; }//记录该子问题的解 memo[amount] = minCount;return minCount; } }

通过备忘录，我们避免了重复计算，即避免重复计算那些已经计算过的子问题。重叠子问题处理模式。

那这种利用重叠子问题的缓存来提升速度的方法是不是万灵药呢？有一句老话，叫计算机中不存在“银弹”，也就是说没有任何一种方法能够解决世界上的所有问题，通过备忘录的思想来处理重叠子问题的方法亦是如此。

1、因为有些问题是不存在重叠子问题的，比如八皇后问题。既然没有重叠子问题，那么通过备忘录来对其优化加速，又从何谈起呢？

2、有些问题虽然看起来像包含“重叠子问题”的子问题，但是这类子问题可能具有后效性，但我们追求的是无后效性。所谓无后效性，指的是在通过 A 阶段的子问题推导 B 阶段的子问题的时候，我们不需要回过头去再根据 B 阶段的子问题重新推导 A 阶段的子问题，即子问题之间的依赖是单向性的。所以说，如果一个问题可以通过重叠子问题缓存进行优化，那么它肯定都能被画成一棵树。希望你能牢记这些限制，不然可能抓破头皮都没法解决问题，最后陷入死胡同。

1.2.3、总结

备忘录的思想极为重要，特别是当求解的问题包含重叠子问题时，只要面试的问题包含重复计算，你就应该考虑使用备忘录来对算法时间复杂度进行简化，具体来说，备忘录解法可以归纳为：

1、用数组或哈希表来缓存已解的子问题答案，并使用自顶向下的递归顺序递归数据；

2、基于递归实现，与暴力递归的区别在于备忘录为每个求解过的子问题建立了备忘录（缓存）；

3、为每个子问题的初始记录存入一个特殊的值，表示该子问题尚未求解（像求解硬币找零问题中的初始值-2）；

4、在求解过程中，从备忘录中查询。如果未找到或是特殊值，表示未求解；否则取出该子问题的答案，直接返回。

与此同时，在求解最优解问题的时候，画出基本的递归树结构，能极大地降低问题的难度。因此在解决此类问题的时候要尝试使用这个方法。

含有备忘录的递归算法已经与动态规划思想十分相似了，从效率上说也是如此。没错！备忘录让我们实现了对算法时间复杂度的“降维打击”（一般会从指数级别到线性级别），这与贪心算法到递归的进步程度不同，这是真正意义上的动态规划思维：我们考虑了整体最优；在计算的过程中保存计算当中的状态，并在后续的计算中复用之前保存的状态。记住使用备忘录来优化你的算法时间复杂度，它是提高算法效率的高级手段。我们距真正的动态规划咫尺之遥，除了重叠子问题，我们还需要理解动态规划中的最优子结构，状态转移方程。

1.3、动态规划解决硬币找零

对于322. 零钱兑换真正的动态规划解法与前面讲到的备忘录记忆化递归到底有什么区别呢？

1.3.1、动归问题的特征

我们曾不止一次提到重叠子问题，并在上一节对其做了深入探讨。其实，重叠子问题是考虑一个问题是否为动态规划问题的先决条件，除此之外，我还提到了无后效性，所以总结下来动态规划问题一定具备以下三个特征：

1、重叠子问题：在穷举的过程中（比如通过递归），存在重复计算的现象；

2、无后效性：子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策的影响

3、最优子结构：子问题之间必须相互独立，或者说后续的计算可以通过前面的状态推导出来（能通过子问题的最优解推导出原问题的最优解）

1.3.2、什么是最优子结构？

1、什么叫子问题之间必须相互独立？

场景1：

苹果原价：8元/斤，梨原价：7元/斤；但是现在做促销，苹果：5元/斤，梨：4元/斤。

问题1：以最低的价格购买5斤苹果，3斤梨。

方案1：显然两种水果的促销价格相互独立，互不影响，我们直接购买即可，都能享受到两种水果的促销价格。

场景2：苹果原价：8元/斤，梨原价：7元/斤；但是现在做促销，苹果：5元/斤，梨：4元/

斤，但是两种水果的折扣不能同时享用。

问题2：以最低的价格购买5斤苹果，3斤梨。

方案2：此时不能同时以最低的苹果价格和最低的香蕉价格享受到最低折扣了。为了使价格最低，我们选择苹果按促销价，梨用原价。

总结：在方案二中，因为子问题并不独立，苹果和香蕉的折扣价格无法同时达到最优，这时最优子结构被破坏

2、什么叫做后续的计算可以通过前面的状态推导？

即：能通过子问题的最优解推导出原问题的最优解

还是在刚刚的场景1中：如果你准备购买了 5 斤折扣苹果，那么这个价格（即子问题）就被确定了，继续在购物车追加 3 斤折扣香蕉的订单，只需要在刚才的价格上追加折扣香蕉的价格，就是最低的总价格（即答案）或者再举一个场景

A : "2+2+2+2+2=? 请问这个等式的值是多少? "

B : "计算ing 。。。。。。结果为10 "

A : "那如果在等式左边写上 1+ ，此时等式的值为多少? "

B : "quickly 结果为11 "

A : “你怎么这么快就知道答案了”

A : "只要在10的基础上加1就行了 "

A : "所以你不用重新计算因为你记住了第一个等式的值为10 ,动态规划算法也可以说是’记住求过的解来节省时间

最后，让我们回到硬币找零的问题上来，它满足最优子结构吗？

答案是满足，假设有两种面值的硬币coins=[3,5]，目标兑换金额为 amount=11。原问题是求这种情况下求最少兑换的硬币数？

如果你知道凑出 amount=6 最少硬币数为 “2”（注意，这是一个子问题），那么你只需要再加 “1”枚面值为 5 的硬币就可以得到原问题的答案，即 2 + 1 = 3。

原问题并没有限定硬币数量，你应该可以看出这些子问题之间没有互相制约的情况，它们之间是互相独立的。因此，硬币找零问题满足最优子结构，可以使用动态规划思想来进行求解。

1.3.3、状态转移方程

当动态规划最终落到实处，就是一个状态转移方程，这是一个吓唬人的名词。没关系，其实我们已经具备了写出这个方程的所有工具。现在我们一起看看如何写出这个状态转移方程。

1、首先，任何穷举算法（包括递归在内）都需要一个终止条件。那么对于硬币找零问题来说，终止条件是什么呢？当剩余的金额为 0 时结束穷举，因为这时不需要任何硬币就已经凑出目标金额了。在动态规划中，我们将其称之为初始化状态。

2、找出子问题与原问题之间会发生变化的变量。原问题指定了硬币的面值，同时没有限定硬币的数量，因此它们俩无法作为“变量”。唯独剩余需要兑换的金额amount是变化的，因此在这个题目中，唯一的变量是目标兑换金额amount。在动态规划中，我们将其称之为状态/状态参数。同时，你应该注意到了，这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。

3、当我们确定了状态，那么什么操作会改变状态，并让它不断逼近初始化状态呢？每当我们挑一枚硬币，用来凑零钱，就会改变状态。在动态规划中，我们将其称之为决策/选择。

总之：构造了一个初始化状态 -> 确定状态参数 -> 设计决策的思路。我们可以写出这个状态转移方程了。通常情况下，状态转移方程的参数就是状态转移过程中的变量，即状态参数。而函数的返回值就是答案，在该题目里是最少兑换的硬币数。

我在这里先用递归形式（伪代码形式）描述一下状态转移的过程

DP(coins, amount) {res = MAX for c in coins // 作出决策，找到需要硬币最少的那个结果 res = min(res, 1 + DP(coins, amount-c)) // 递归调用 if res == MAX return -1 return res }

不知你是否发现，这个状态转移方程与刚开始定义递归的递推公式是一样的。

在上一节为了优化递归中的重叠子问题，设计了一个缓存用于存储重叠子问题的结果，避免重复计算已经计算过的子问题。而这个缓存其实就是存储了动态规划里的状态信息。

因此，带备忘录的递归算法与你现在看到的动态规划解法之间，有着密不可分的关系。它们要解决的核心问题是一样的，即消除重叠子问题的重复计算。

事实上，带备忘录的递归算法也是一种动态规划解法。但是，我们并不把这种方法作为动态规划面试题的常规解法，为什么呢？这是递归带来的固有问题。

1、首先，从理论上说，虽然带备忘录的递归算法与动态规划解法的时间复杂度是相同规模

的，但在计算机编程的世界里，递归是依赖于函数调用的，而每一次函数调用的代价非常高昂。递归调用是需要基于系统堆栈才能实现的。而对于基于堆栈的函数调用来说，在每一次调用的时候都会发生环境变量的保存和还原，因此会带来比较高的额外时间成本。这是无法通过时间复杂度分析直接表现出来的，表现在空间复杂度上，递归的空间复杂度跟递归的深度有关系。

2、更重要的是，即便我们不考虑函数调用带来的开销，递归本身的处理方式是自顶向下的。

比如斐波拉契数列用递归处理的递归状态树如下

每次都需要查询子问题是否已经被计算过，如果该子问题已经被计算过，则直接返回备忘录中的记录。也就是说，在带备忘录的递归解法中，无论如何都要多处理一个分支逻辑，只不过这个分支的子分支是不需要进行处理的。这样的话，我们就可以预想到，如果遇到子问题分支非常多，那么肉眼可见的额外时间开销在所难免。我们不希望把时间浪费在递归本身带来的性能损耗上。

那么，有什么好的办法来规避这个问题呢？我们需要设计一种新的缓存方式，并考虑使用迭代来替换递归，这也是动态规划算法真正的核心。

1.3.4、状态缓存与循环

在带备忘录的递归算法中，每次都需要查询子问题是否已经被计算过。针对这一问题，我们可以思考一下，是否有方法可以不去检查子问题的处理情况呢？在执行 A 问题的时候，确保 A 的所有子问题一定已经计算完毕了。仔细一想，这不就是把处理方向倒过来用自底向上嘛。

回顾一下自顶向下的方法，我们的思路是从目标问题开始，不断将大问题拆解成子问题，然后再继续不断拆解子问题，直到子问题不可拆解为止。通过备忘录就可以知道哪些子问题已经被计算过了，从而提升求解速度。那么如果要自底向上，我们是不是可以首先求出所有的子问题，然后通过底层的子问题向上求解更大的问题

比如下图中表示了斐波拉契数列自底向上的处理方式

从解路径的角度看动态规划的自底向上处理方式，那么它的形式可以用一个数组来进行表示，而这

个数组事实上就是实际的备忘录存储结构

这样有一个好处，当求解大问题的时候，我们已经可以确保该问题依赖的所有子问题都已经计算过

了，那么我们就无需检查子问题是否已经求解，而是直接从缓存中取出子问题的解。通过自底向上，我

们完美地解决掉了递归中由于“试探”带来的性能损耗。

这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

1.3.5、求解零钱兑换

1、确定状态参数和选择

原问题：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

子问题：

输入：coins = [1, 2, 5], amount = 9 输出：3 解释：9 = 5 + 2 + 2

我们发现在原问题和子问题之间发生变化的是兑换金额amount

因此兑换金额 amount 就是状态参数，而选择也很简单，从 coins 中选择硬币会使得 amount 发送变化。

2、定义dp数组的含义：

dp[i] 的含义是：如果能从 coins 中找到相应的硬币凑成总金额 i ，那么 dp[i] 则为所需的最少的硬币个数。

注意：

1、对于每一个兑换金额 i 都有两种可能，一种能从 coins 中找到硬币凑成，一种是不能从

coins 中找到硬币凑成。

2、如果能凑成则 dp[i] 代表所需的最少硬币个数。因此在这里我们给 dp 数组中先填充一个不可能的值，比如 -1,Integer.MAX_VALUE,Integer.MIN_VALUE 等，后续状态转移的时候如果 dp[i] 能凑成功，则修改 dp[i] 的值。

在本题中，我们最终要返回的就是 dp[11]

3、确定初始状态：

当兑换金额 i=0 时，所需最少硬币个数为0，因此初始状态 dp[0]=0 。 4、状态转移逻辑：

动态规划的核心，先计算子问题，再由子问题推导计算父问题；也就是说在我知道了 dp[i-1] 及更小子问题的值后我如何根据这些计算 dp[i] ：也就是说：

可以理解为现在已经有了以下这些条件

能从 coins 中找到凑成金额 i-1 的最少硬币个数为 dp[i-1] ，现在要凑成金额 i ，

能从 coins 中找到凑成金额 i-2 的最少硬币个数为 dp[i-2] ，现在要凑成金额 i ，

…

能从 coins 中找到凑成金额 0 的最少硬币个数为 dp[0] ，现在要凑成金额 i ,

如何凑成金额 i 呢？答案很简单：

从 coins 中依次选择硬币 coin ，能跟它正好凑成金额 i 的是 i-coin ，那凑成金额 i-coin 的最少硬币已经算出来了，就是子问题 dp[i-coin] ，在它的基础上我们选择了一个金额为 coin 的硬币，故： dp[i]=dp[i-coin]+1当然 coins 中有很多金额的硬币可选择，每选择一个都会得到一个 dp[i] 的值，我们要求的是最小值，所以： dp[i]=min(dp[i],dp[i-coin]+1)

翻译成代码为：

for (int coin:coins) {if (coin <= i) {//代表该硬币可选 dp[i] = min (dp[i],dp[i-coin]+1);}}

5、代码实现

class Solution {public int coinChange(int[] coins, int amount) {//构造dp数组(缓存中间的状态信息/子问题的最优解/状态参数的值) int[] dp = new int[amount+1]; //初始填充一个不可能的值,对应面额amount最多的组合就是amount个1的组合，需要 amount个硬币,所以amount+1是不可能的 Arrays.fill(dp,amount+1); //初始状态赋值 dp[0] = 0;//amount=0无需硬币组合 // 对每种状态的每种取值进行遍历 //从子问题开始求解,推导到大问题，外层循环遍历所有状态的所有取值 for (int i=1;i<=amount;i++) {//对每个子问题i，在coins中找能满足子问题i的众多解中的最优解(最少硬币数量)， 内层 for 循环在求所有选择的最小值 for (int coin:coins) {if (coin <= i) {//coin>子问题i，该硬币无法构成最终解,直接跳过 /* 1:直接从dp中拿出求解问题i所依赖的子问题(i-coin)的最优解, 2:dp[i-coin] + 1即当前子问题i选择该coin的最优解 3:dp[i] = Math.min(dp[i],dp[i-coin]+1);是在众多解中选出一个 最优的作为子问题i的最优解。 */ dp[i] = Math.min(dp[i],dp[i-coin]+1); }} }return (dp[amount]==amount+1) ? -1:dp[amount]; } }

1.3.6、通用的动态规划

掌握了如何使用标准的动态规划来解决硬币找零问题后，我们需要将相关的解法来进行推广，以此推导出一套解决动态规划面试问题的通用框架，或者说套路。注意，这里是一个经验总结。

动态规划问题的核心是写出正确的状态转移方程，为了写出它，我们要先确定以下几点：

1、状态参数：找出子问题与原问题之间会发生变化的变量。在硬币找零问题中，这个状态只有一个，就是剩余的目标兑换金额 amount；一般来说，状态转移方程的核心参数就是状态。

2、决策/选择：改变状态，让状态不断逼近初始化状态的行为。在硬币找零问题中，挑一枚硬币，用来凑零钱，就会改变状态，状态不断向初始化状态的变化过程就是状态转移。

3、定义 dp 数组/函数的含义。我们需要自底向上地使用备忘录来消除重叠子问题，构造一个备忘录（在硬币找零问题中的dp数组。为了通用，我们以后都将其称之为 DPtable），dp中存储的值就是我们想要的结果。

dp数组跟我们的状态参数有关，状态参数不止一个，一般dp数组是多维的。

4、初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端。在硬币找零问题中，这个初始化状态是 dp[0]=0；

5、状态转移逻辑：自下而上的解决方式就是，思考如何根据子问题的解去推导父问题的解，在该题目中就是如何根据 dp[i-1] 及更小的子问题的解，来推导 dp[i]

通过这样几个简单步骤，我们就能写出状态转移方程：

在此也给出解决动态规划的通用框架如下：

//定义dp，可以是数组/哈希 int[][].... // 初始化 base case dp[0][0][...] = base //进行状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...)

计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门。

1.3.7子序列系列

子序列：在原数据序列中删除某些数据（也可以不删）后的新数据序列，会破坏原有数据的连续性。

子串：是原有数据串的一个子部分，

子序列类型的问题，如果穷举基本上复杂度都很高，指数级别，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列类型的问题，十有八九都需要动态规划来解决，能把复杂度降低到 n^2

300. 最长上升子序列

https://leetcode-/problems/longest-increasing-subsequence/

通过前面对动态规划思想的讲述，发现状态转移的逻辑部分不太容易想到，其实状态转移逻辑的思

考有一个技巧叫做：数学归纳法思想

如果我们想通过数学归纳法证明一个结论：

1、先假设这个结论在 k<n 时成立，

2、然后想办法证明 k=n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于

k 等于任何数都成立。类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0…i−1] 都已经被算出来了，然后问自己：怎么通过这些结果算出 dp[i] ？

对于最长上升子序列这道题，我们的算法分析如下：

首先最长上升子序列，是一定要保证严格上升特性。

比如nums=[1,3,3,4,6,8,7]，但[1,3,3,4,6,7]并不满足，[1,3,4,6,7]才是。

1、状态参数：

我们发现nums数组的下标 i 是这中间的变量。

2、决策/选择

原问题，求nums=[1,3,3,4,6,8,7]的最长上升子序列长度，

子问题，求nums=[1,3]的最长上升子序列长度 123

从子问题到原问题的过程（从左到有遍历nums）中状态会发生变化

3、定义dp数组的含义

重要：大部分情况下我们题目要返回的数据就是dp数组中存储的值，或者通过dp数组中存储的值处

理后可得到。

我们的定义是这样的：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

根据这个定义，我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。

//构造dp数组,对dp[i]而言也是取各组合中的最大值 ........构造dp数组........ //返回dp中的最大值 int res = 0; for (int i = 0; i < dp.length; i++) {res = Math.max(res, dp[i]); }return res;

4、初始化状态

nums长度为0，则最长上升子序列长度为0，nums长度1（只有一个元素），则最长上升子序列1 5、状态转移逻辑

我们说动态规划的一个思想就是先解决子问题，然后由子问题去推导大问题的解决；这个推导过程

我们可以用数学归纳法思想：

如果我们已经知道了子问题， dp[0] ~ dp[5] 的值了，如何通过这些值去推导出 dp[5]

根据 dp 数组的定义，现在想求 dp[5] 的值，也就是想求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最

后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即

可。

for (int j=0;j<=i;j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i],dp[j]+1); } }

6、代码实现

class Solution {public int lengthOfLIS(int[] nums) {//定义dp int[] dp = new int[nums.length]; //初始化,dp[0]=1,其实任意dp[i]初始化值都可以等于1,因为都可以将自己当作子序列 Arrays.fill(dp,1); //状态转移 for (int i=0;i<nums.length;i++) {for (int j=0;j<i;j++) {if (nums[j] < nums[i]) {//从dp[i]所有组合中找最长的长度 dp[i] = Math.max(dp[i],dp[j] +1);}} }//返回dp[i]中的最大值 int max = dp[0]; for (int i=1;i<dp.length;i++) {max = Math.max(max,dp[i]); }return max;} }//简化版本 class Solution {public int lengthOfLIS(int[] nums) {//定义dp int[] dp = new int[nums.length]; //初始化,dp[0]=1,其实任意dp[i]初始化值都可以等于1,因为都可以将自己当作子序列 Arrays.fill(dp,1); int max=0; //状态转移for (int i=0;i<nums.length;i++) {for (int j=0;j<i;j++) {if (nums[j] < nums[i]) {//从dp[i]所有组合中找最长的长度 dp[i] = Math.max(dp[i],dp[j] +1); } }max = Math.max(max,dp[i]); }return max; } }

复杂度：时间复杂度O(N^2)，空间复杂度O(N)

7、总结

1、一定明确 dp 数组所存数据的含义。这非常重要，如果不得当或者不够清晰，会阻碍之后的步

骤。

2、根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0…i−1] 都已知，想办法求出 dp[i]

3、如果无法完成第二步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或

者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

2、动态规划题目

1143. 最长公共子序列

https://leetcode-/problems/longest-common-subsequence/

最长公共子序列（Longest Common Subsequence，简称 LCS）的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，对于两个字符串求子序列的问题，都是用两个指针i和j分别在两个字符串上移动，大概率是动态规划思路。

算法分析：

1、确定状态参数和选择：

原问题：

输入：text1 = "abcde", text2 = "ace" 输出：3 "ace"

子问题：

输入：text1 = "abc", text2 = "ac" 输出：2 "ac"

状态参数有两个： text1 中 [1,i] 个字符， text2 中 [1,j] 个字符数选择就很简单，从前到后遍历字符串，增加text1,text2 中的字符，遇到相同的字符就选择作为LCS中的一个字符，遇到不同的就不选。

2、定义dp数组的含义

dp[i][j] 的含义是：对于 text1[1…i] 和 text2[1…j] ，它们的 LCS 长度是 dp[i][j] 。

text1="ace",text2="babcde"

d[2][4] 的含义就是：对于 “ac” 和 “babc” ，它们的 LCS 长度是 2。

这里要注意的是 i,j 并非指的是字符的下标。

而我们最终想得到的答案应该是 dp[3][6] 。

3、确定初始条件：

dp[0][…]=0 ： text1 是空串，则LCS肯定是0

dp[…][0]=0 ： text2 是空串，则LCS也肯定是0

4、状态转移逻辑

状态转移，其实就是做选择，这里做选择就是从前到后遍历字符串，遇到相同的字符就选择作为lcs 中的字符，遇到不同的字符，要么 text1 增加一个字符,要么 text2 增加一个字符，要么同时增加一个字符。

根据动态规划的思想，我们要思考应该如何从子问题的结果推导到大问题，即通过前面求解的值如何推导出现在所求的值。

这里有四种情况：

t1[i] == t2[j]：该字符一定是lcs中的一个字符,dp[i][j]=dp[i-1][j-1] +1t1[i] != t2[j]：又分三种小情况， dp[i][j] 的值取这三种情况中的最大值，因为最终要返回的是最长的公共子序列dp[i][j] 可由以下三个子问题解推导出来：

t1 增加一个字符， dp[i][j]=dp[i][j-1]

t2 增加一个字符， dp[i][j]=dp[i-1][j]

t1,t2 均增加一个字符，注意大前提是增加完后 t1[i] != t2[j]，因此 dp[i][j]=dp[i-1] [j-1]

之： dp[i][j] 最终的取值应该是： d[i][j] =MAX(dp[i-1][j],dp[i-1][j-1],dp[i][j- 1])

但是，其实最终的取值只需要满足： dp[i][j]=MAX(dp[i-1][j],dp[i][j-1]) ，原因如下图

这样一看，显然 dp[i-1][j-1] 对应的 lcs 长度不可能比前两种情况大，所以没有必要参与比较。我们只需要找谁能让 lcs 最长，就听谁的。

状态转移的逻辑总结如下：

if (text1[i] == text2[j]) {// 这边找到一个 lcs 的元素，继续往前找dp[i][j] = dp[i-1][j-1] + 1; }else {//谁能让 lcs 最长，就听谁的 //dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]); dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); }

代码实现

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] t1 = text1.toCharArray();char[] t2 = text2.toCharArray();//定义dp数组int n=t1.length;int m=t2.length;int[][]dp=new int[n+1][m+1];//初始化状态 dp[0][...]=0,dp[...][0] = 0for(int i=0;i<n;i++){dp[i][0]=0;}for(int i=0;i<m;i++){dp[0][i]=0;}//状态转移for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(t1[i-1]==t2[j-1]){// 这边找到一个 lcs 的元素，继续往前找dp[i][j]=dp[i-1][j-1]+1;}else{//谁能让 lcs 最长，就听谁的 //dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1],dp[i][j- 1]);dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);}}}return dp[n][m];}}

可自行在dp table中 分析状态转移的过程

相似的题目

583. 两个字符串的删除操作

https://leetcode-/problems/delete-operation-for-two-strings/

class Solution {public int minDistance(String word1, String word2) {char[] t1 = word1.toCharArray(); char[] t2 = word2.toCharArray(); int n=t1.length;int m=t2.length;int[][]dp=new int[n+1][m+1];for(int i=0;i<=n;i++){dp[i][0]=i;}for(int i=0;i<=m;i++){dp[0][i]=i;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(t1[i-1]!=t2[j-1]){dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;}else{dp[i][j]=dp[i-1][j-1];}}}return dp[n][m];}}

712. 两个字符串的最小ASCII删除和

https://leetcode-/problems/minimum-ascii-delete-sum-for-two-strings/

class Solution {public int minimumDeleteSum(String s1, String s2) {char[]t1= s1.toCharArray();char[]t2= s2.toCharArray();int n=t1.length;int m=t2.length;int[][]dp=new int[n+1][m+1];//把值放进去是关键for(int i=1;i<=n;i++){dp[i][0]=dp[i-1][0]+t1[i-1];}for(int j=1;j<=m;j++){dp[0][j]=dp[0][j-1]+t2[j-1];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(t1[i-1]==t2[j-1]){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=Math.min(dp[i-1][j]+t1[i-1],dp[i][j-1]+t2[j-1]);}}}return dp[n][m];}}

72. 编辑距离

https://leetcode-/problems/edit-distance/

算法分析：

1、确定状态参数和选择：

原问题：

输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

子问题：

输入：word1 = "hor", word2 = "ro" 输出：2 解释： hor -> ho (删除 'r') ho -> ro (将 'h' 替换为 'r')

状态参数也有两个： word1 中 [1,i] 的字符， word2 中 [1,j] 的字符

做决策/选择的过程就是：两个指针 i 和 j 分别在 word1 和 word2 上从左到右遍历（或者从右到左）

从左到右遍历是从子问题到大问题；从右到左是从原问题到子问题。

2、定义dp数组的含义

dp[i][j] 的含义是：将 word1[1…i] 转换成 word2[1…j] 所使用的最少操作步数。

比如：

输入：word1 = "rad", word2 = "apple" 输出：5 需要注意的是：将`word1`转成成`word2`，和将`word2`转换成`word1`所使用的最少操作步 数是一样的。

dp[2][4] 的含义就是将 word1=“ra” 转换成 word2=“appl” 使用的最少操作步骤为4；

这里要注意的是 i,j 并非指的是字符的下标。

当然对于原问题，我们最终返回 dp[3][5] 即可。

3、确定初始条件：

如果 word1="" 并且 word2="" ，不需要任何操作，即 dp[0][0]=0

如果 word1="" 但是 word2 不为空串，则最少的操作步数就是 word2 串的长度，即 dp[0][j]=j

如果 word1 不为空串，但是 word2="" ，则最少的操作步数就是 word1 串的长度，即 dp[i][0]=i

4、思考状态转移逻辑：

由题设条件，我们能采取三种操作：

插入一个字符；

删除一个字符；

替换一个字符。

题目给定了两个单词，设为 A 和 B，这样我们就能够六种操作方法。

但我们可以发现，如果我们有单词 A 和单词 B：

对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为dog 时，我们既可以删除单词 A 的最后一个字符 e，得到相同的 dog，也可以在单词 B 末尾添加一个字符 e，得到相同的 doge；

同理，对单词 A 插入一个字符和对单词 B 删除一个字符也是等价的；

对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为cat 时，我们修改单词 A 的第一个字母 b -> c，和修改单词 B 的第一个字母 c -> b 是等价的。

这样以来，本质不同的操作实际上只有三种：

在单词 A 中插入一个字符；对单词 A 删除一个字符；修改单词 A 的一个字符。

基于动态规划的思想，我们要考虑如何通过子问题的解来推导大问题的解。

最终:在这种情况下,dp[i][j]有三种可能的取值,而我们要取得是三种可能中的最小值

即:dp[i][j]=min(dp[i][j-1+1,dp[i-1][j]+1,dp[i-1][j-1]+1)

当我们获得 dp[i][j-1] ， dp[i-1][j] 和 dp [i-1][j-1] 的值之后就可以计算出 D[i] [j] 。 dp[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j个字符，我们在 A 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i][j- 1] + 1 ；

dp[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第i 个字符，我们在 B 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i-1][j] + 1 ；

dp[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的 第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 dp[i][j] 最小可以为 dp[i- 1][j-1] + 1 。特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下， dp[i][j] 最小可以为 dp[i-1][j-1] 。

翻译过来的转移逻辑是：

if (word1[i] == word2[j]) {//不用操作，继承之前的结果 dp[i][j] = dp[i-1][j-1]; }else {//找三种操作中能让编辑距离最小的 dp[i][j] = min(dp[i-1][j] +1,dp[i][j-1] +1, dp[i-1][j-1] +1); }

代码实现

class Solution {public int minDistance(String word1, String word2) {char[]w1=word1.toCharArray();char[]w2=word2.toCharArray();//定义dp数组int n=w1.length;int m=w2.length;int [][]dp=new int[n+1][m+1];//初始条件 dp[0][j] = j,dp[i][0] = i;for(int i=0;i<=n;i++){dp[i][0]=i;}for(int j=0;j<=m;j++){dp[0][j]=j;}//状态转移for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(w1[i-1]==w2[j-1]){//唯一的一种操作,跳过(i,j),dp[i][j]继承自dp[i-1][j-1]dp[i][j]=dp[i-1][j-1];}else{/* 删除操作：dp[i][j] = dp[i-1][j] +1 插入操作：dp[i][j] = dp[i][j-1] +1; 替换操作：dp[i][j] = dp[i-1][j-1] +1; */dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;}}}return dp[n][m];}}

5. 最长回文子串

https://leetcode-/problems/longest-palindromic-substring/

算法分析：

1、确定状态参数和选择

原问题：

输入: "babad" 输出: "bab

子问题：

输入: "aba" 输出: "aba

这里因为对于输入的字符串 s=“cbbd” 它的任意一个字串都是它的子问题，比如找 cbb ， bbd它们的最长回文子串。

这道题也是一道经典的区间dp问题。因此区间的起始位置和结束位置就是在原问题和子问题之间发生变化的变量，故：

状态参数有两个：字符串的起始位置 i 和结束位置 j ，这里的 i 和 j 代表的就是下标了。

选择也很简单：改变区间的大小，

2、定义dp数组的含义

dp[i][j] 的含义是：对于字串 s[i…j] 是否是回文串，为 true 表明 s[i…j] 是回文串，否则不是。

要注意的是：

1：这里 dp 数组中存储的值不能直接作为题目返回的结果，以前我们说大部分情况下，dp数

组中存储的就是我们想要的返回结果，在这里要做一个变形，最终返回的最长回文子串是什么呢？

i 和 j 就是字串的左右边界，我们要返回的是所有 dp[i][j]==true 的选项中，最长的那个字串。

dp[1][2] 的含义就是：子串 bb 是回文子串， dp[0][2] 表明子串 cbb 不是回文子串

当然在此处的 i 和 j 代表的就是下标了。

而我们最终要返回的是：所有 dp[i][j]==true 的子串中，长度最长的子串。

3、确定初始状态

因为 i 和 j 代表了子串的左右边界，满足 i<=j， 所以初始状态为：当 ij ，只有一个字符，肯定

是回文串，即当 ij 时： dp[i][j]=true

另外当 i>j 时不符合我们字串的定义，所以 dp[i][j]=false 。

4、状态转移逻辑

状态转移，需要数学归纳法思维，说白了就是如何从已知的结果推出未知的部分，如何根据子

问题的解推导原问题的解，这样定义容易归纳，容易发现状态转移关系。

在这里原问题是求： dp[i][j] ，子问题是 dp[i+1][j-1] 甚至更小的子问题。

也就是说如果我们想求 dp[i][j] ，假设已经求出来子问题 dp[i+1][j-1] 的结果

（s[i+1…j-1] 是回文字串，或者不是回文字串）或者更小的子问题的结果，你是否能想办法算

出 dp[i][j] 的值（ s[i…j] 是否是回文字串）

为了讨论一个字串是否是回文串，我们从回文串的定义出发：

如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；如果一个字符串的头尾两个字符相等，才有必要继续判断下去。

如果里面的子串是回文，整体就是回文串；

如果里面的子串不是回文串，整体就不是回文串。

翻译出来的逻辑就是

if (s[i] != s[j]) {//字符串的头尾两个字符都不相等，那么一定不是回文串dp[i][j] = false; }else {//字符串的头尾两个字符相等,它是否是回文串取决于它的字串s[i+1...j-1] dp[i][j] = dp[i+1][j-1]; }

需要注意：

当 s[i]=s[j] 时我们说 s[i…j] 是否是回文串取决于它的子串 s[i+1…j-1] 是否是回文串，这样当这个字串区间不断缩小时，会遇到的边界情况就是： [i+1,j-1] 并不能构成区间，即这个区间的长度小于2，即：

(j-1) - (i+1)<2 推导得到： j-i<3 ，等价于子串 s[i…j] 的长度等于2或者等于3。

举个例子：现在子串 s[i…j] 为 aba 或者为 aa ，满足 s[i]==s[j] ，此时 s[i+1…j-1] 为 “b” 或者是空串 “”

显然：

如果子串 s[i + 1… j - 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 1 个字符，显然是回文；

如果子串 s[i + 1… j - 1] 为空串，那么子串 s[i, j] 一定是回文子串。

因此状态转移的逻辑修改如下：

if (s[i] != s[j]) {//字符串的头尾两个字符都不相等，那么一定不是回文串dp[i][j] = false; }else {//字符串的头尾两个字符相等,它是否是回文串取决于它的字串s[i+1...j-1]if (j-i<3) {dp[i][j] = true;//s[i+1...j-1]为边界情况，只有一个字符或者是空串。 }else {dp[i][j] = dp[i+1][j-1];} }

代码

class Solution {public String longestPalindrome(String s) {//特殊判断if(s==null||s.length()<2){return s;}char[]strs= s.toCharArray();int n=strs.length;/* 定义dp数组:dp[i][j]代表字串s[i ... j]是否是一个回文串 最终返回的在所有dp[i][j]为true的组合中,(j-i+1)值最大的那个 */boolean[][]dp=new boolean[n][n];//确定初始化状态 dp[i][i] = true,当i>j时dp[i][j] = false;for(int i=0;i<n;i++){dp[i][i]=true;}//定义最大回文字串的开始位置和长度int begin=0;int length=1;//状态转移for(int j=1;j<n;j++){for(int i=0;i<j;i++){//如果s[i] != s[j]那么 s[i ... j]肯定不是回文串if(strs[i]!=strs[j]){dp[i][j]=false;}else{/* 如果s[i] == s[j],此时还不能直接下结论s[i ... j]是回文串， 还得看它的子串s[i+1 ... j-1]是不是回文串， 如果s[i+1 ... j-1]是那么s[i ... j]肯定也是 */if(j-i<3){dp[i][j]=true;}else{dp[i][j]=dp[i+1][j-1];}}// 只要 dp[i][j] == true ，就表示子串 s[i..j] 是回文，此时记录最大 回文长度和起始位置if(dp[i][j]&&(j-i+1)>length){length=j-i+1;begin=i;}}}return s.substring(begin,begin+length);}}

需要注意：

1、根据状态转移方程， dp[i][j] 是由 dp[i+1][j-1] 转移而来。为了保证每次计算 dp[i][j] 时 dp[i+1][j-1] 的值都被计算出来了，我们采用的遍历方式需要注意，如下图

这种遍历也是可以的

516. 最长回文子序列

https://leetcode-/problems/longest-palindromic-subsequence/

算法分析：

1、确定状态参数和选择：

原问题：

输入:"dcbbd" 输出:4 解释：一个可能的最长回文子序列为 "dbbd"

子问题：

输入:"cbb" 输出:2 解释：一个可能的最长回文子序列为 "bb"。

这里因为对于输入的字符串 s=“dcbbd” 它的任意一个字串都是它的子问题，比如找 dcb ， cbbd 它们的最长回文子序列。

这道题是一道经典的区间dp问题。因此区间的起始位置和结束位置就是在原问题和子问题之间发生变化的变量，故：

状态参数有两个：字符串的起始位置 i 和结束位置 j ，这里的 i 和 j 代表的就是下标了。

选择也很简单：改变区间的大小，

改变区间共三种情况：

两边都扩大， i 和 j 分别向两边扩张

i 向左边扩张

j 向右边扩张

2、定义dp数组的含义：

在子串s[i…j]中，最长回文子序列的长度为 dp[i][j] 。

要注意的是：

1、 s[i…j]中最长回文子序列跟回文串还不一样 ，回文串中， dp[i][j] 代表的是 s[i…j]

是否是回文串，而最长回文子序列 dp[i][j] 代表的是在子串 s[i…j] 中的回文子序列，这个子

序列有可能就是子串 s[i…j] ，也可能是 s[i…j] 中的一部分或某几部分，因此 dp[i][j] 没

法单独代表字串 s[i…j] 是否是回文子序列。

举个例子：

输入："bbbab" 输出：4解释：最长的回文子序列是："bbbb" 123

3、确定初始状态

输入："bbbab" 输出：4 解释：最长的回文子序列是："bbbb" 123

因为 i 和 j 代表了子串的左右边界，满足 i<=j， 所以初始状态为：当 ij ，只有一个字符，最长回文子序列肯定是1，即当 ij 时： dp[i][j]=1

另外当 i>j 时不符合我们字串的定义，所以 dp[i][j]=0 。

4、状态转移逻辑

状态转移，需要数学归纳法思维，说白了就是如何从已知的结果推出未知的部分，如何根据子问题的解推导原问题的解，这样定义容易归纳，容易发现状态转移关系。

在这里原问题是求： dp[i][j] ，子问题是 dp[i+1][j-1] 甚至更小的子问题。

也就是说如果我们想求 dp[i][j] ，假设已经求出来子问题 dp[i+1][j-1] 的结果（ s[i+1…j-1] 中最长回文子序列的长度）或者更小的子问题的结果，你是否能想办法算出dp[i][j] 的值（ s[i…j] 中，最长回文子序列的长度）

if (s[i] == s[j])// 它俩一定在最长回文子序列中 dp[i][j] = dp[i + 1][j - 1] + 2; else //看 s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？ dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

5、代码实现

class Solution {public int longestPalindromeSubseq(String s) {char[]cr=s.toCharArray();//获取字符串长度int n=s.length();int[][]dp=new int[n][n];//初始化条件,当i==j时,dp[i][j] =1;当i>j的所有选项dp[i][j]=0;for(int i=0;i<n;i++){dp[i][i]=1;}//状态转移,这里dp[i][j]的值每次是由其左边，下边，左下边三个位置计算出来的，为了 保证这一点，只能斜着遍历或者反着遍历，我们选择反着遍历for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){if(cr[i]==cr[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][n-1];}}

需要注意两点：

1：初始条件里面，对于那些 i > j 的位置，根本不存在什么子序列，应该初始化为 0。

2：根据状态转移方程，想求 dp[i][j] 需要知道 dp[i+1][j-1] ， dp[i+1][j] ， dp[i][j-1] 这三个位置的值，为了保证每次计算 dp[i][j] ，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历：

6、总结

找到初始化条件和状态转移逻辑之后，一定要观察 DP table，看看怎么遍历才能保证通过已计算出

来的结果解决新的问题。

题目(背包和打家劫舍系列)

背包系列

要论经典的动态规划问题，首先想到的就是背包问题，其实背包又分很多种，大多数人首先遇到的

其实是背包中的0-1背包。

1、0-1背包

1.1、问题描述

给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 和价值 v 两个属性，那么第 i个物品的重量为 w[i]，价值为 v[i]。现在让你用这个背包装物品，每种物品可以选0个或1个，问最多能装的价值是多少？

示例： 输入：W = 5, N = 3 w = [3, 2, 1], v = [5, 2, 3] 输出：8 解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

1.2、算法分析和实现

1、首先想能否对w和v排序？

答案是不能，因为一旦重新排序后，w[i] 和 v[i] 对应的不一定是同一个物品了。

2、一看到最多的价值，判断出这是一个最优化问题，首先想到贪心。那么贪心算法的局部最优能解决我们的问题吗？

事实上不太能，因为如果按照贪心算法来解的话，每次都找价值最大的，且重量在合理范围内。因为可能涉及到要对价值数组v进行排序，而本题如果排序是不可行的。另外贪心的局部最优不见得能保证全局最优。

3、要获得整体最优解，我们貌似只能进行穷举，既然涉及到穷举我们就要优先想是否能用动态规划

来解决这个问题。因此首先判断该题是否满足动态规划的特征呢？

1：是否具有重叠子问题，对于 0-1 背包问题来说，即便我们不画出求解树，也能很容易看出在穷举的过程中存在重复计算的问题。这是因为各种排列组合间肯定存在重叠子问题的情况

2：无后效性：当我们选定了一个物品后，它的重量与价值就随即确定了，后续选择的物品不会对当前这个选择产生副作用。因此，该问题无后效性；

示例： 输入：W = 5, N = 3 w = [3, 2, 1], v = [5, 2, 3] 输出：8 解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

3：最优子结构：当我们选定了一个物品后，继续做决策时，我们是可以使用之前计算的重量和价值的，也就是说后续的计算可以通过前面的状态推导出来。因此，该问题存在最优子结构。

4、既然可以用动态规划解决解决，下面按照动态规划是思路来求解

1：寻找状态参数，

在原问题和子问题之间发生变化的变量，

当我们将某个物品 i 放入 背包中后，1、背包内物品的数量n在增加,可选择的物品在减少，它是一个变量；n增加到题设条件N时可选择 物品为0，2、背包的重量在增加,即背包剩余还能装下的重量w在减少，它也是一个变量；w减到0意味着不能 在装物品了

因此，当前背包内的物品数量 N 和背包还能装下的重量 W 就是这个动态规划问题的状态参数

2、如何决策/选择，决策无非就是该不该把当前这个物品放入背包中：放怎么样，不放怎么样

有了状态和选择，拿以前的框架先套一下

for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 择优(选择1，选择2...)

3、明确dp数组的定义

dp数组是什么？其实就是用于存储状态信息的，存储的值就是我们想要的结果（一般就是题

目要求返回的数据）。

现在的状态有两个，也就是说我们需要一个二维 dp 数组，一维表示可选择的物品，一维表示

背包的容量。

dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大

价值是dp[i][w]。

比如说，如果 dp[3][5] = 8，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选 择，当背包容量为 5 时，最多可以装下的价值为 8。 为什么要这么定义？便于状态转移，或者说这就是套路，记下来就行了。

根据这个定义，我们想求的最终答案就是 dp[N][W] 。

此时可以细化我们的动归框架：

int dp[N+1][W+1] for i in [1..N]: for w in [1..W]: dp[i][w] = max( 把物品 i 装进背包 , 不把物品 i 装进背包 ) return dp[N][W]

4、寻找初始化状态，

任何穷举算法（包括递归在内）都需要一个终止条件，这个所谓的终止条件，就是我们在动态

规划解法当中的最初子问题，因此我们将其称作初始化状态。

在 0-1 背包中，这个终止条件是什么呢？ 1、当背包的剩余容量为0 或者 物品的数量为0 时要终止执行。即：不选物品（物品数量为0），或者 背包容量为0 初始化状态就是d[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的 最大价值就是0。

//初始条件： dp[0][..] = 0 dp[..][0] = 0

5、思考状态转移逻辑

简单说就是，上面伪码中「把物品 i 装进背包」和「不把物品 i 装进背包」怎么用代码体现出来

刚刚分析到： dp[i][w] 表示：对于前 i 个物品，当前背包的容量为 w 时，这种情况下可以装下的最大价值是 dp[i][w]

1、如果你没有把这第 i 个物品装入背包，那么很显然，最大价值 dp[i][w] 应该等于 dp[i-1] [w]。你不装嘛，那就继承之前的结果，即前（i-1）个物品在当前容量w下的最大价值。

不把该物品i放入背包的原因是： 1、背包剩余的容量 < 该物品i的重量，物品i想放放不进去，只能不装 2、背包剩余的容量 > 该物品i的重量，物品i可以放进去，但可以选择不装进去

2、如果你把这第i个物品装入了背包，那么最大价值 dp[i][w] 应该等于 dp[i-1][ w - w[i- 1]] + v[i-1] 。

其中不太好理解的就是：`dp[i-1][ w-w[i-1] ] 和 v[i-1]` 现在我们想装第i个物品，并计算这时候的最大价值，我们去找它的子问题 显然，我们应该寻求前`i-1`个物品在剩余重量`w-w[i-1]`限制下能装的最大价值，加上第i个 物品的价值`v[i-1]`，这就是装第i个物品后背包可以装的最大价值。w数组和v数组的下标都取`i-1`的原因是`i`是从1开始的。

综上就是两种选择，我们都已经分析完毕，也就是写出来了状态转移方程，可以进一步细化代码：

for i in [1..N]: for w in [1..W]: dp[i][w] = max( dp[i-1][w] , dp[i-1][w - w[i-1]] + v[i-1] ) return dp[N][W]

6、把状态转移方程翻译成代码，并处理细节

public class BackPack {public int dp(int[] wt,int[] v,int N,int W) {//1.创建dp数组 int[][] dp = new int[N+1][W+1]; //2.定义初始化状态 //2.1.dp[0][..] = 0 物品个数0,背包有再大的容量最大价值也是0 for (int i=0;i<W+1;i++) {dp[0][i] = 0; }//2.2.dp[..][0]=0 背包容量为0,有再多的物品最大价值也是0 for (int i=0;i<N+1;i++) {dp[i][0] = 0; }//3.套模板,每种状态的每个取值都取值一遍 从子问题开始 for (int i=1;i<N+1;i++) {//物品个数从[1,N] for (int w=1;w<W+1;w++) {//背包容量从[1,W] //4.根据状态转移方程找最优解 1if (wt[i-1] > w) {//4.1 物品i的重量>背包容量，物品i放不进去只能选择不装进去 dp[i][w] = dp[i-1][w]; }else {//4.2 装进去和不装进去两种择优。 放入物品i后的最大价值= 前 (i-1)个物品在(w - wt[i-1])限制下的最大价值 + 当前物品i的价值v[i-1]dp[i][w] = Math.max(dp[i-1][w],dp[i-1][w-wt[i-1]] + v[i-1]); } } }return dp[N][W]; }public static void main(String[] args) {int N = 3, W = 5;// 物品的总数，背包能容纳的总重量 int[] w = {3, 2, 1}; // 物品的重量 int[] v = {5, 2, 3}; // 物品的价值 System.out.println(new BackPack().dp(w,v,N,W)); }}

1049. 最后一块石头的重量 II

https://leetcode-/problems/last-stone-weight-ii/comments/

class Solution {public int lastStoneWeightII(int[] stones) {int n=stones.length;int sum=0;for(int stone:stones){sum+=stone;}int m=sum/2;int [][]dp=new int[n+1][m+1];for(int i=0;i<=n;i++){dp[i][0]=0;}for(int i=0;i<=m;i++){dp[0][i]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(stones[i-1]>j){dp[i][j]=dp[i-1][j];}else{dp[i][j] = Math.max(dp[i - 1][j], stones[i - 1] + dp[i - 1][j -stones[i - 1]]);}}}return sum-2*dp[n][m];}}

2、416. 分割等和子集

https://leetcode-/problems/partition-equal-subset-sum/submissions/

对于这个问题，看起来和0-1背包没有任何关系，但是我们可以将其转换成0-1背包问题，怎么转换？

首先回忆一下0-1背包问题是怎么描述的？

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 w[i] ，价值为 v[i] ，现在让你用这个背包装物品，能装的最大价值是多少？

转换成0-1背包的描述如下：

我们可以先对集合求和，得出 sum ，给一个可装载重量为sum/2的背包和N个物品，每个物品的重量为nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

2.1、解法分析

1、确定状态参数：

状态就是 背包的容量 W 和 可选择的物品N 2、决策/选择：

将物品 i 装入背包，不将物品 i 装入背包。

3、明确dp数组的含义：

dp[i][j]=true 代表，对于前 i 个物品，当前背包的容量为 j 时恰好将背包装满， dp[i] [j]=false 则说明不能恰好将背包装满。

比如说，如果 dp[4][9] = true ，其含义为：对于容量为 9 的背包，若只是用前 4 个物品，可以有一种方法把背包恰好装满。

而对于本题来说它的具体含义是指：对于给定的集合中，若只对前 4 个数字进行选择，存在一个子集的和可以恰好凑出 9。

4、明确初始化状态：

背包容量W=0，肯定存在一种装法，那就是不装；可选择物品 N 为0则肯定不存在一种装法

初始条件就是 dp[…][0] = true 和 dp[0][…] = false ，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。

5、状态转移的逻辑：

针对 dp 数组含义，可以根据我们的选择对 dp[i][j] 得到以下状态转移：

如果不把 nums[i] 算入子集，或者说你不把这第i个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][j] ，继承之前的结果。

如果把 nums[i] 算入子集，或者说你把这第i个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i - 1][j-nums[i-1]] 。

1、由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i- 1]

2、 dp[i - 1][j-nums[i-1]] 也很好理解：你如果装了第 i 个物品，就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。

换句话说，如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。

6、代码实现

class Solution {public boolean canPartition(int[] nums) {//将问题转换成0-1背包问题， /* 对nums求和为sum,该问题转换为,给你N个物品和sum/2容量大小的背包,是否存在一种 能将背包恰好装满的方法。 1.确定状态：容量，物品个数 2.选择/决策：将物品i装入背包,将物品i不装入背包.3.初始状态：容量为0,存在一种放法，为true。物品个数为0肯定不存在满足条件的放 法为false。 4.明确dp数组的含义, dp[i][j],前i个物品在背包容量为j下是否存在一种装法刚好 装满 初始条件:dp[0][...] =false; dp[...][0]=true; 5.状态转移逻辑： 不将物品i放入背包,返回值由dp[i-1][j]决定 将物品i放入背包，返回值由dp[i-1][j-nums[i-1]]决定 *///求和int max=0;int sum=0;for(int num:nums){sum+=num;max=Math.max(max,num);}//剪枝1,如果所有数的和为奇数,则肯定不存在有i个物品重量和为 sum/2；if(sum%2!=0){return false;}//剪枝2 如果集合中的最大数大于sum/2则肯定不存在这种组合if(max>sum/2){return false;}int n=nums.length;int m=sum/2;boolean[][]dp=new boolean[n+1][m+1];//初始化for(int i=0;i<=m;i++){dp[0][i]=false;}for(int i=0;i<=n;i++){dp[i][0]=true;}//状态转移for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(nums[i-1]>j){//物品i背包放不下那只能选择不放进去,因此是否有一种满足条件的放法取 决 (i-1)物品在容量j限制下是否满足dp[i][j]=dp[i-1][j];}else{//背包能放下物品i,但是也可以选择放和不放,最终是否满足题意取决放或者 不放的结果 //当物品i放入背包时,最终的结果取决与(i-1)物品在( j - num[i-1] )限制下的结果。dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];}}}return dp[n][m];}}

时间复杂度：O(N * M)

空间复杂度：O(N * M)

2.2、状态压缩

对于刚刚的代码是否还能优化？

通过分析代码，我们发现一个问题， dp[i][j] 都是通过上一行 dp[i-1][…] 转移过来的，之前的数据都不会再使用了。

所以，我们可以进行状态压缩，将二维 dp 数组压缩为一维，降低空间复杂度

class Solution {public boolean canPartition(int[] nums) {int max=0;int sum=0;for(int num:nums){sum+=num;max=Math.max(max,num);}if(sum%2!=0){return false;}if(max>sum/2){return false;}int n=nums.length;int m=sum/2;boolean[]dp=new boolean[m+1];dp[0]=true;for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){//注意这里需要从大到小if(nums[i-1]<=j){dp[j]=dp[j]||dp[j-nums[i-1]];}}}return dp[m];}}

压缩到一维dp之后，内层循环我们需要从大到小计算，为什么？

1、 dp[i][j] 的取值都是从上一行 dp[i-1][…] 转移过来的，并且是从上一行的该列或该列的前面几列转移过来的

2、压缩后dp中存储的是上一行中每一列的取值，每个 i 的取值在内层循环结束后dp中存储的就是该行每列的取值了，然后进入到下一行。

3、如果列从小到大更新，内层循环每计算一次会将dp中的值修改为当前行该列的值，当我们在计算后面列的时候，dp中存储的就不再是上一行对应列的取值了。

4、但是如果是从大到小更新就不存在这个问题了。

优化后代码的时间复杂度：O（N * M），空间复杂度：O(M)

另外该题还有非动态规划解法，利用剪枝+回溯！

注意：压缩后的状态只跟背包的容量有关了

进阶： 0-1 背包问题：

474. 一和零 https://leetcode-/problems/ones-and-zeroes/

475. 目标和 https://leetcode-/problems/target-sum/

476. 盈利计划 https://leetcode-/problems/profitable-schemes/

3、518. 零钱兑换 II

https://leetcode-/problems/coin-change-2/

把这个问题转化为背包问题的描述形式：

有一个背包，最大容量为 amount ，有一系列物品 coins ，每个物品的重量为 coins[i] ，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的完全背包问题

算法解析：

1、明确状态参数和决策

状态有两个，就是 背包的容量 和 可选择的物品 ，选择就是 装进背包 或者 不装进背包 。

2、定义dp数组

dp[i][j] 的定义如下：使用前i个物品，当背包容量为j时，有 dp[i][j] 种方法可以装满背包。不

同于以前的是物品可以使用多次

翻译回我们题目的意思就是：使用coins中的前i个硬币的面值，若想凑出金额j，有 dp[i][j] 种凑

法。

3、初始化状态

初始化状态为： dp[0][…] = 0， dp[…][0] = 1 。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“不凑”就是唯一的一种凑法。

最终想得到的答案就是 dp[N][amount] ，其中 N 为 coins 数组的大小。

4、状态转移逻辑

本题的不同点在于物品的数量是无限的，因此状态转移逻辑如下：

如果你不把这第i个物品装入背包，也就是说你不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第i个物品装入了背包**，也就是说你使用 coins[i] 这个面值的硬币，那么 dp[i] [j] 应该等于 dp[i][j-coins[i-1]]** 。

由于 i 是从 1 开始的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。

dp[i][j-coins[i-1]] 代表如果用这个面值的硬币，接着只需关注如何凑出金额 j - coins[i-1]

综上两种选择，而我们想求的 dp[i][j] 又代表了共有多少种凑法，所以 dp[i][j] 的值应该是以上两种选择的结果之和

5、代码实现

class Solution {public int change(int amount, int[] coins) {int n=coins.length;int[][]dp=new int[n+1][amount+1];for(int i=0;i<=amount;i++){dp[0][i]=0;}for(int i=0;i<=n;i++){dp[i][0]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){if(j<coins[i-1]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]];}}}return dp[n][amount];}}

时间复杂度：O( N * amount)，空间复杂度：O（N * amount）

6、进一步优化，状态压缩

class Solution {public int change(int amount, int[] coins) {int n=coins.length;int[]dp=new int[amount+1];dp[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=amount;j++){if(j>=coins[i-1]){dp[j]=dp[j]+dp[j-coins[i-1]];}}}return dp[amount];}}

注意此处：

1、一维dp中保存的是上一行的dp值，

2、内存循环从小到大原因是：

当前行的状态值要么直接等于上一行该列的状态值，

要么等于上一行当前列的值 dp[j] +当前行前面列的值 dp[j-coins[i-1]] ，因此要从小到大来计算。

如果从大到小计算上面的 dp[j-coins[i-1]] 还是上一行前面列的值，并不是当前行的，因为当前行的还没被修改。

注意：压缩后的状态只跟amount有关了！

打家劫舍系列

198. 打家劫舍

https://leetcode-/problems/house-robber/

算法分析：

1、确定状态参数

要注意的是：由题意可得，原问题和子问题之间并不是所给的房间个数变少了。而是我可以选择从某个位置开始偷，一直偷到最后面。

原问题：从第一间房子开始偷，一直偷到最后

输入：[1,2,3,1] 输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

子问题：从第三间房子开始偷，一直偷到最后

输入：[1,2,3,1] 输出：3 解释：偷窃 3 号房屋 (金额 = 3)。

由此可见，给定的房间数组 int[] nums 的下标 i 就是我们的状态参数

2、确定选择

选择也很简单，强盗从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢

3、定义dp数组的含义

dp[i]=x 的含义是：从下标为 i 的房子开始抢，一直到最后所能抢到的最高金额为 x 。

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

dp[1]=3 代表的是强盗从第二间房屋开始抢到最后所能抢到的最大金额是3.

而本题我们最终需要返回的是： dp[0] ,从第一间房屋就开始做选择

4、确定初始状态

强盗从左到右走过这一排房子，在每间房子前可以选择抢或者不抢，当它走过了最后一间房子后，就没得抢了，能抢到的钱显然是 0

因此初始条件为： dp[nums.length]=0

5、状态转移逻辑

按照我们的选择，强盗从左到右走过这一排房子，在每间房子前都有两种选择：抢或者不抢。

如果你抢了 i 这间房子，那么你肯定不能抢相邻的下一间房子了，只能从下下间房子 i+2 开始做选择。此时 dp[i]=dp[i+2]+nums[i] ,其中 nums[i] 就是我在房间 i 抢到的money。

如果你不抢 i 这间房子，那么你可以走到下一间房子 i+1 前，继续做选择，此时dp[i]=dp[i+1]

在两个选择中，每次都选更大的结果，最后得到的就是最多能抢到的 money

dp[i] = Math.max(dp[i+1],dp[i+2] + nums[i]);

6、代码实现

class Solution {//dp解法 public int rob(int[] nums) {int n = nums.length;//定义dp数组 int[] dp = new int[n+2]; //初始化状态 dp[n] = dp[n+1] = 0;/* 状态转移,先从子问题开始求解 i=n-1:就是最后一间房,它依赖(i+1)和(i+2)，故dp数组的长度为:n+2 初始条件则为: dp[n] = dp[n+1] = 0; */for (int i=n-1;i>=0;i--) {dp[i] = Math.max(dp[i+1],nums[i]+ dp[i+2]); }return dp[0]; } }

7、思考状态是否能压缩

我们发现状态转移只和 dp[i] 最近的两个状态 dp[i+1] ， dp[i+2] 有关，所以可以进一步优化，

将空间复杂度降低到 O(1)。

class Solution {public int rob(int[] nums) {int n=nums.length;//发现状态转移只和dp[i]最近的两个状态dp[i+1]，dp[i+2]有关,进一步优化状态空间int dp=0;int dp_1=0;int dp_2=0;for(int i=n-1;i>=0;i--){dp=Math.max(dp_1,dp_2+nums[i]);//以前的dp_i_1转移后成为了dp_i_2,dp_i转移后成为了dp_i_1dp_2=dp_1;dp_1=dp;}return dp;}}

进阶：

213. 打家劫舍 II https://leetcode-/problems/house-robber-ii/

核心原则就是：第一个和最后一个不能同时抢。 所以：要么不抢第一个，要么不抢最后一个。 注意，不抢第一个的时候，最后一个可抢可不抢；另一种情况同理 取两种情况中的最大值

class Solution {public int rob(int[] nums) {if(nums==null||nums.length==0){return 0;}if(nums.length==1){return nums[0];}int[] dp1 = new int[nums.length];int[] dp2 = new int[nums.length];dp1[1] = nums[0]; //从第1个房屋开始偷dp2[1] = nums[1]; //从第2个房屋开始偷for(int i=2;i<nums.length;i++){dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);}return Math.max(dp1[nums.length-1],dp2[nums.length-1]);}}

打家劫舍 III https://leetcode-/problems/house-robber-iii/

/*** Definition for a binary tree node.* public class TreeNode {*int val;*TreeNode left;*TreeNode right;*TreeNode(int x) { val = x; }* }*/class Solution {public int rob(TreeNode root) {int []result=robInternal(root);return Math.max(result[0],result[1]);}public int[]robInternal(TreeNode root){int []result=new int[2];if(root!=null){int []left=robInternal(root.left);int []right=robInternal(root.right);// 0 表示不偷根节点，那么可以选择下一个偷或不偷的最大值result[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);// 1 表示偷根节点result[1]=left[0]+right[0]+root.val;}return result;}}