动态规划：自底向上、由小及大回溯法：自顶向下、由大及小
例如：得到一个数字12345，动态规划会将原问题12345分割为子类问题1234+当前问题5，思考新增的那个数字会对最优解造成怎样的影响，找初始值、找递推关系式、找最优解；而回溯法则会从12345开始思考，一步一步向下遍历，遍历1、遍历2……遍历5。
动态规划(dynamicprogramming)：它是把研究的问题分成若干个阶段，且在每一个阶段都要“动态地”做出决策，从而使整个阶段都要取得最优效果。
理解：其实，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存历史记录的状态，一般是用一维数组或者多维数组来保存。
理解：若当前元素为第i个，那么前i个状态下的最优解=前i-1个状态下的最优解+当前抉择
注意：得是连续的，因为数组是连续的顺序表，你得把数组填满，才能获得答案！得是递推的，如今的状态是根据以前的状态递推出来的。这里与回溯法不同的是，回溯法以前的状态不一定是最佳状态，回溯法只是将所有可能性都遍历完了；而动态规划以前的状态必须是最佳状态，每一次递推都是从以前的最佳状态开始递推，比较有大局观。
比如说剪绳子问题，它会跟你说给你一根长度为n的绳子，那么我们可以考虑一下n-1或者n-2是不是能推出n。。
题目只问最优值，并没有问最优解，因此绝大多数情况下可以考虑使用「动态规划」的方法。理解：由于动态规划是一个填表的过程，所以表格中只会有某个数值，也就是说，我们只能去找到最优值，而不是最优解或最优集。最优值：集合内元素和的最大值（如99）最优解：集合内元素和为最大的集合（如[90,9]）
前后数据有关
原问题可分解为子类问题
关键词：为n时的结果，阶段，递推，最优值
动态规划的思路与分治法极为相似，都是由原问题=子类问题+当前问题这个公式推导而来，我们的阶段问题记录表就是我们的子类问题，而我们的当前问题就是利用子类问题推导出来解决的。
如1..n=1..n-1+n
技巧：使用下面的方式，表示不可达，以免做加减运算的时候会越界
1.明确数组的含义：建立数组，明确数组元素的含义。分解策略必须能够使我们对当前节点状态有一定的认知，能够成功划分子类问题进行递推。
数组dp[]：原问题=子类问题+当前问题
这里需要注意，动态规划的状态不是当前第i个，而是前i个累计的状态。理解：动态规划与回溯法异曲同工，类似于回溯递归到第i层，此时的结果是累计了前i次操作得出来的，一步一步走到第n层，即可得到我们最终所需的最优解。
注意：阶段一定要和数组一样是连续的，我们只有填满数组，才能获得答案；比如说，01背包的背包重量容量状态，我们其实有效的也就那么几个值，容量一个一个增加物品也放不进去，但是我们还是得连续的一个一个向上增加，因为我们这数组是一个连续的表，并不能让我们从中空出几个，并且，空出几个也不利于我们的递推填表，我们需要填满整个表，才能得出我们的答案！
这里要注意的是，我们的动态规划是不同于递归的，递归不需要记录当前阶段的状态就能知道该走哪一步，慢慢走下去，而我们的动态规划是迭代方法，需要不停记录当前阶段的状态（数组保存的状态一般都具有前缀性，即数组保存的一般是包含了前几个状态在内的最优值），否则可能就找不着东南西北了。
而我们的数组就是记录状态的好东西！！！
这里你可以想想01背包问题，二维数组的一维下标记录了当前选择的物品编号（前i个物品分配情况的阶段，这种编码一般都具有前缀性质，即考虑了之前编号的数据），二维下标记录了当前背包总容量（容量递增的阶段），下标对应的数值状态记录了背包总价值。它们三个合起来，我们就能知道不同阶段的不同状态信息，我们就可以递推出所有信息！！！！！
理解：其实，数组就是一般的阶段状态记录，我们要选取合适维度的数组来记录我们所拥有的信息，每一个数组元素及其下标都应该对应着一个阶段的状态。
递归、回溯法的状态是记录当前位置的状态，并非当前位置的最优状态，因为没有办法知道当前位置是否为最优，我们只能知道我们当前路线的当前位置的状态，而不知道其他路线的当前位置的状态，并且没有办法保存当前位置的最优状态，毕竟是递归，数据就不断地刷新了。
可以理解成486，只有回溯能力，不能保证回溯的当前位置状态最优。
而动态规划记录的是当前位置的最优状态，动态规划可以知道其他路线的位置最优状态。
它比较有大局观，每次都统筹规划，从最优的状态选择中不断前进！
也就是说，与递归、回溯法不同，回溯法只能知道当前的状态是怎样的，并不能保证当前的状态是最优的，它的优势在于遍历所有可能性；而动态规划则是每一步都通过规划，保证当前状态最优，它的优势在于统筹规划，每次都是最优的。
根据数组，制作阶段问题表1.制作阶段记录表：根据数组建表，之后会填入初始值，最后利用递推关系式写程序推出其他空表项。
注意：这个是为我们通过初始值和递推关系式写出程序提供可视化条件以及思路，把抽象的东西可视化了，时时刻刻都知道自己要干嘛。当然，如果脑子里有思路可以忽略。。
2.寻找最小问题（寻找数组初始值）：寻找数组元素初始值的出口，这个出口最好写在最前面，我们的结果就是用数组初始值结合下面的递推关系式得出来的；
注意：这个初始值要特别的给出一个出口，因为它们不是被递推出来的。以免后面设置的初始值越界，比如数组dp[1]容量为1，结果初始值设置了dp[2]的值，就越界了。
技巧：我们也可以通过递推关系式下标索引的越界，来反向推理得到我们应该初始化的范围，如对于递推关系式包含下标i-1和i-2，我们为了避免越界，我们就应该为下标为0、1的元素进行初始化，避免其越界。
例如：
//初始值出口if(n<=2){ returnn;}有时候问题过于复杂，导致初始值能找到，但是可能由于状态过多，考虑不周、找不全。
这种情况下，我们可以从下面的递推关系式的条件入手
如递推关系式为dp[i][0][j]=Math.max(dp[i-1][0][j],dp[i-1][1][j-1]+prices[i]);，我们可以看到一维下标包含i-1，三维下标包含j-1，所以我们的数组初始值需要将dp[0][x][x]和dp[x][x][0]包含其中给解决掉，不然当i和j为0时，遍历就会超出数组边界。
如子类问题为dp[leftIndex+1][rightIndex-1]，我们可以看到此子类问题的规则：
3.划分子类问题（找出递推关系式）：明确递推范围（即dp[i]与它后几位有关？），找出数组元素递推关系式。
注意：可以从dp[i]=这一数学公式开始推想，寻找我们的递推范围，比如说青蛙跳台阶一次可以跳1格或2格，所以我们的递推范围为2，即dp[i]与dp[i-1]和dp[i-2]有关。
并且需要注意，我们的初始值已经填入进去了，我们得从没有填数据的位置开始填表。
原问题=子类问题+当前问题原问题可能不止与一个子类问题有关，因为问题的划分方式多种多样，子类问题与当前问题也多种多样，遇到这种情况可以考虑所有之内问题与当前问题，多次填表，之后再将多次填表的结果组合成原问题的结果。
原问题：[10,9,2,5,3,7,101,18]以18为尾的子序列长度子类问题：[10,9,2,5,3,7,101]以101为尾的子序列长度、[10,9,2,5,3,7]、[10,9,2,5,3]、...、[10]当前问题：18，每次与子类问题的尾进行大小比较，推出原问题
子类问题需要多次填表，需要额外的一层循环。
并且根据子类问题的规则，我们可以倒推出我们的最小问题（初始问题）：如子类问题为dp[leftIndex+1][rightIndex-1]，我们可以看到此子类问题的规则：
填表顺序与子类问题的大小层级有关，我们的填表顺序需要保证子类问题慢慢增大（由小及大），利用小子类问题的结果推出大子类问题的结果，直到推出原问题结果。也就是说，我们最好能按照子类问题的大小层级进行填表，而不是按照我们的表格遍历顺序
实例：
前缀分解dp[index]：一般是顺序填表，一行一行地填表。
原问题：[1,2,3,4,5]、子类问题：[1,2,3,4]、当前问题：5子类问题的大小：[1]、[1,2]、[1,2,3]、[1,2,3,4]、[1,2,3,4,5]从最小问题一步步递推到原问题；所以我们的填表顺序：dp[0]->dp[1]->dp[2]->dp[3]->dp[4]
原问题：babab、子类问题：aba、当前问题：bb子类问题的大小：b、aba、babab所以我们的填表顺序：dp[2][2]->dp[1][3]->dp[0][4]，可以看到我们第一层级窗口大小为1，第二层级窗口大小为3，第三层级窗口大小为5所以我们的最终填表顺序：窗口大小1、3、5，这样会比上面一种跳跃式填表更具有逻辑性，并且程序会更加好写。
如上一步我们找到了dp[i]与dp[i-1]和dp[i-2]有关，这一步我们就需要解决，dp[i]与dp[i-1]和dp[i-2]之间的递推关系式。
递推关系式的筛选直接决定了整个算法的递推效率，例如下面的题《322.零钱兑换》，两种递推方法，带来的算法效率大有不同。
我们要根据当前的历史记录表，找到能够直接递推出当前元素的某个递推关系式，注意是直接，越直接，我们的递推效率越高。
就拿零钱兑换这题举例，我的思路是按总金额的增减进行递推；而答案是直接按硬币的增减进行递推，所以答案的递推效率会更高。
第一步：定义数组元素的含义。上面说了，我们会用一个数组，来保存历史记录，假设用一维数组dp[]吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，即你的dp[i]是代表什么意思？
那么下面我来举个例子吧！问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
首先，拿到这个题，我们需要判断用什么方法，要跳上n级的台阶，我们可能需要用到前几级台阶的数据，即历史记录，所以我们可以用动态规划。我们需要存储的信息：
所以我们使用一维数组：
然后依据上面我说的第一步，建立数组dp[]，那么顺理成章我们的dp[i]应该规定含义为：跳上一个i级的台阶总共有dp[i]种解法。那么，求解dp[n]就是我们的任务。
注意：这里一维表比较简单可能体现不出它的作用，到二维表它就能很方便的将数据可视化了。
此题，由于明确了数组的含义，我们可以确定是一张一维表。
历史记录表：
第二步：找出初始值。利用我们学过数学归纳法，我们可以知道如果要进行递推，我们需要一个初始值来推出结果值，也就是我们常说的第一张多米诺骨牌。
本题的初始值很容易我们就找出来了，
第三步：找出数组元素之间的关系式。动态规划有一点类似于数学归纳法的，当我们要计算dp[n]时，是可以利用dp[1]……dp[n-2]、dp[n-1]，来推出dp[n]的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如，dp[i]=dp[i-1]+dp[i-2]，这个就是它们的递推关系式了。而这一步，也是最难的一步，后面我会讲几种类型的题来说。
当n=i时，即有i级台阶，我们的青蛙最后究竟怎么样到达的这第i级台阶呢？因为青蛙的弹跳力有限，只能一次跳一级或者两级，所以我们有两种方式可以到达最后的这第i级：
所以，我们只需要把青蛙跳上i-1级台阶和i-2级台阶的跳法加起来，我们就可以得到到达第i级的跳法（i≥3），即
这样我们知道了初始值dp[1]、dp[2]，可以从dp[3]开始递推出4、5、6、...、n。
用程序循环得出后面的空表项。
你看有了初始值，以及数组元素之间的关系式，那么我们就可以像数学归纳法那样递推得到dp[n]的值了，而dp[n]的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。
答案：
//青蛙跳台阶intf(intn){ //特别给初始值的出口 if(n<=2) returnn; //创建数组保存历史数据 int[]dp=newint[n+1]; //给出初始值 dp[1]=1; dp[2]=2; //通过递推关系式来计算出dp[n] for(inti=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } //把最终结果返回 returndp[n];}状态数组定义技巧其实，我们的动态规划算法，根据状态数组的定义不同，我们也会有不同的解法，当然，这些解法都是可以得到正确答案的，大家可以按照自己的思维去决定怎么定义状态数组。
下面总结了几种常用的状态数组定义技巧。
理解：下面的所有方法都可以概括为一句话——数组保存的状态一般都具有前缀性，此数组的该状态存储的是前几个中的最优值。
适用场景：要求元素连续、窗口
如连续子数组的最大和
为何定义最大和\(dp[i]\)中必须包含元素\(nums[i]\)：保证\(dp[i]\)递推到\(dp[i+1]\)的正确性；如果不包含\(nums[i]\)，递推时则不满足题目的连续子数组要求。
原理：其实就是限定末尾下标为i的那个元素必须包含。
示例操作：dp[i]=Math.max(dp[i-1]+nums[i],nums[i])
适用场景：范围、区间、不连续、一维
原理：不限定下标为i的那个元素必须包含，只代表范围。
示例操作：dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
适用场景：j取值0、1表示两种状态（加入或不加入），背包问题（前i个物品，容量为j，利用i来消除排列组合的重复性（优化中会提到））二维，比较通用
原理：完整的表明当前状态，方便递推。
示例操作：dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1])和dp[i][1]=dp[i-1][0]+nums[i]
上面的这些方法，下面都会讲的！
前缀性
区间DP属于线性DP的一种，以区间长度作为DP的阶段，以区间的左右端点作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。阶段(长度)、状态(左右端点)、决策三者按照由外到内的顺序构成三层循环。
注意：所有子类问题都需要由小及大求解，区间由小及大的方式为区间长度。
当要租用游艇从一个站到另外一个站时，中间可能经过很多站点，不同的停靠站策略就有不同的租金。
树形DP一般自底向上，将子树从小到大作为DP的“阶段”，将节点编号作为DP状态的第1维，代表以该节点为根的子树。
树形DP一般采用深度优先遍历，递归求解每棵子树（分治法，每次递归返回每棵子树的最优值），回溯时从子节点向上进行状态转移。在当前节点的所有子树都求解完毕后，才可以求解当前节点。（也可以广度优先遍历，使用拓扑排序，依次从叶子节点（入度为0）开始向上遍历。
注意：所有子类问题都需要由小及大求解，树形由小及大的方式为子树大小，从叶子节点向上，到小子树，到中子树，到大子树。
记忆化搜索，当搜索到之后存入数组，如果数组中有值，则直接返回。
题目描述(POJ2342/HDU1520)：Ural大学将举行80周年校庆晚会。大学职员的主管关系像一棵以校长为根的树。为了让每-一个人都玩的嗨皮，校长不希望职员和他的直接上司都在场。人事处已经评估了每个职员的欢乐度,你的任务是列出一个邀请职员名单，使参会职员的欢乐度总和最大。
输入：职员的编号从1到N。输入的第一行包含数字N(1≤N≤6000)。后面的N行中的每一行都包含相应职员的欢乐度。欢乐度是一个从-128到127整数。之后的N-1行是描述主管关系树。每一行都具有以下格式:LK,表示第K名职员是第L名职员的直接主管。输入以包含00的行结尾。
输出：输出参会职员欢乐度的最大和值。
输入样例：
输出样例：
5答案明确数组含义：
dp[u][0]表示不选择节点u时，在以节点u为根的子树中参加职员的欢乐度最大和。
dp[u][1]表示选择节点u时，在以节点u为根的子树中参加职员的欢乐度最大和。
原问题：当前节点u为根的树的最大欢乐度（选或不选），max(dp[root][0],dp[root][1])，root为树根
子类问题：u的子节点为根的子树的最大欢乐度
当前问题：当前节点u选或不选
最小问题：叶子节点dp[u][0]=0,dp[u][1]=val[u];
dfs：分治法
//E[u]为邻接表voiddfs(intu){ dp[u][0]=0; dp[u][1]=val[u]; for(inti=0;i //E[u]为邻接表int[]dfs(intu){ dp[u][0]=0; dp[u][1]=val[u]; for(inti=0;i 除了root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 给定二叉树的root。返回在不触动警报的情况下，小偷能够盗取的最高金额。 输入:root=[3,4,5,1,3,null,1]输出:9解释:小偷一晚能够盗取的最高金额4+5=9答案方法一：动态规划思路与算法 简化一下这个问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。 我们可以用f(o)表示选择o节点的情况下，o节点的子树上被选择的节点的最大权值和；g(o)表示不选择o节点的情况下，o节点的子树上被选择的节点的最大权值和；l和r代表o的左右孩子。 至此，我们可以用哈希表来存f和g的函数值，用深度优先搜索的办法后序遍历这棵二叉树，我们就可以得到每一个节点的f和g。根节点的f和g的最大值就是我们要找的答案。 我们不难给出这样的实现： classSolution{Map 我们可以做一个小小的优化，我们发现无论是f(o)还是g(o)，他们最终的值只和f(l)、g(l)、f(r)、g(r)有关，所以对于每个节点，我们只关心它的孩子节点们的f和g是多少。我们可以设计一个结构，表示某个节点的f和g值，在每次递归返回的时候，都把这个点对应的f和g返回给上一级调用，这样可以省去哈希表的空间。 代码如下。 classSolution{publicintrob(TreeNoderoot){int[]rootStatus=dfs(root);returnMath.max(rootStatus[0],rootStatus[1]);}publicint[]dfs(TreeNodenode){if(node==null){returnnewint[]{0,0};}int[]l=dfs(node.left);int[]r=dfs(node.right);intselected=node.val+l[1]+r[1];intnotSelected=Math.max(l[0],l[1])+Math.max(r[0],r[1]);returnnewint[]{selected,notSelected};}}复杂度分析 空间复杂度：\(O(n)\)。虽然优化过的版本省去了哈希表的空间，但是栈空间的使用代价依旧是\(O(n)\)，故空间复杂度不变。 如何枚举？枚举[0,386]区间的所有数时，首先从百位开始枚举，百位可能是0、1、2、3。枚举时不超过386即可。（树形图） 数位DP需要注意的几个问题：（1）记忆化。无限制时，可以记忆化；有限制时，不可以记忆化，需要继续根据限制枚举。枚举[0,386]区间的所有数，当百位是02时，十位和个位枚举没有限制，都是一样的，采用记忆化递归，只需计算一次并将结果存储起来，下次判断若已赋值，则直接返回该值即可。百位是3时，十位限制在08；十位是07时，个位无限制；十位是8时，个位限制在06。（2）上界限制。当高位枚举刚好达到上界时，紧接着的下一位枚举就有上界限制了。可以设置一个变量limit标记是否有上界限制。（3）高位枚举0。为什么高位需要枚举0？这是因为百位枚举0相当于此时枚举的这个数最多是两位数，若十位继续枚举0，则枚举的是一位数。枚举小于或等于386的数，一位数、两位数当然也比它小，所以高位要枚举0。（4）前导0。有时会有前导0的问题，可以设置一个lead变量表示有前导0。例如统计数字里面0出现的次数。若有前导0，例如008，数字8不包含0，则不应该统计8前面的两个0。若没有前导0，例如108，则应该统计8前面的1个0。 题目描述(HDU3555):反恐怖分子在尘土中发现了一枚定时炸弹，但这次恐怖分子改进了定时炸弹。定时炸弹的数字序列从1到n。若当前的数字序列包括子序列“49”，则爆炸的力量会增加一个点。现在反恐人员知道了数字n,他们想知道最后的力量点。 输入：输入的第1行包含一个整数T(1≤T≤10000)，表示测试用例的数量。对每个测试用例，都有一个整数n(\(1≤n≤2^{63}-1\))作为描述。。输出：对每个测试用例，都输出一个整数，表示最终的力量点。 3150500输出样例： 0115答案状态表示：dp[pos][sta]表示当前第pos位在sta状态下满足条件的个数，sta表示前一位是否是4，布尔变量。 状态转移方程：if(sta&&i==9)ans+=limitn%z[pos-1]+1:z[pos-1];z[pos]表示\(1O^{pos}\)，若无限制，则“49”后面有多少位，就累加z[pos-1]的个数。若有限制，则求出“49”后面的数字再加1。 例如，[1,500]区间，枚举时“49”后面还有1位数，无限制，则累加10个包含“49”的数，分别为490~499。例如，[1,496]区间，枚举时“49”后面的数字是6，有限制，则累加6+1个（包括0）包含“49”的数，即490~496。z[pos]表示\(10^{pos}\)，若无限制，则“49”后面有多少位，累加z[pos-1]的个数。若有限制，则求出“49”后面的数字再加1。 计算[1,500]区间有多少个数包含“49”。(1)数字分解:dig[1]=0，dig[2]=0,dig[3]=5。(2)从高位开始，当前位是3，前面1位不是4，有限制。len=dig[3]=5，枚举i=0..5。 (3)累加结果，返回[1,500]区间包含“49”的数15个。 给你一个正整数n，请你返回区间[1,n]之间特殊整数的数目。 示例1： 输入：n=20输出：19解释：1到20之间所有整数除了11以外都是特殊整数。所以总共有19个特殊整数。示例2： 输入：n=5输出：5解释：1到5所有整数都是特殊整数。示例3： 将n转换成字符串s，定义\(f(i,\textit{mask},\textit{isLimit},\textit{isNum})\)表示构造从左往右第i位及其之后数位的合法方案数，其余参数的含义为： 后面两个参数可适用于其它数位DP题目。 枚举要填入的数字，具体实现逻辑见代码。 下面代码中Java/C++/Go只需要记忆化\((i,\textit{mask})\)这个状态，因为： 一般来说，动态规划使用一个一维数组或者二维数组来保存状态。 比如42.接雨水中，我们使用一维数组dp[i]表示下标i左边最高柱子的高度。dp[i]包含了两个信息： 比如10.正则表达式匹配中，我们使用二维数组dp[i][j]表示字符串s的前i项和t的前j项是否匹配。dp[i][j]包含了三个信息： 对于本题来讲，通过分析，我们也可以表示类似的状态，dp[i][j]表示当第i行的座位分布为j时，前i行可容纳的最大学生人数。但如果我们还想知道第i行有多少个座位呢？这无疑多了一个维度，这时我们不能用类似dp[i][j][k]来表示了，因为计算机中没有类似三维的数据结构。 这时候状态中所包含的信息过多，该怎么办呢？我们可以利用二进制以及位运算来实现对于本来应该很大的数组的操作，这就是状态压缩，而使用状态压缩来保存状态的DP就叫做状态压缩DP。 可以使用位编码记录每一行的状态 比如判断是否当前状态有1相邻。 (j&(j<<1))!=0||(j&(j>>1))!=03.判断此行(第i行)状态j与上一行(第i-1行)状态k的关系我们需要将此行i的状态j与上一行i-1的所有状态k，相互比较，迭代填表。 注意：本题相对原题稍作改动 输入：[1,2,3,1]输出：4解释：选择1号预约和3号预约，总时长=1+3=4。示例2： 输入：[2,7,9,3,1]输出：12解释：选择1号预约、3号预约和5号预约，总时长=2+9+1=12。示例3： 输入：[2,1,4,5,3,1,1,3]输出：12解释：选择1号预约、3号预约、5号预约和8号预约，总时长=2+4+3+3=12。dp[i]表示以元素nums[i]结尾的最优的预约时长其实也就是限定下标为i的那天接受预约。（下面还有不限定的情况，需要分类讨论，大家可以看看） 当nums[i]为结尾，必定选中的情况下，总预约时长可分为两种情况，求最大值 方法二：设计一维状态变量第1步：定义状态dp[i]：区间[0，i]里接受预约请求的最大时长。 第2步：状态转移方程这个时候因为不限定下标为i这一天是否接受预约，因此需要分类讨论： 二者取最大值，因此状态转移方程为dp[i]=max(dp[i-1],dp[i-2]+nums[i])。 第3步：思考初始化看状态转移方程，下标最小到i-2，因此初始化的时候要把dp[0]和dp[1]算出来，从dp[2]开始计算。 第4步：思考输出由于定义的状态有前缀性质，并且对于下标为i的这一天也考虑了接受预约与不接受预约的情况，因此输出就是最后一天的状态值。 参考代码2： publicclassSolution{publicintmassage(int[]nums){intlen=nums.length;if(len==0){return0;}elseif(len==1){returnnums[0];}elseif(len==2){ returnMath.max(nums[0],nums[1]); }//dp[i]：区间[0,i]里接受预约请求的最大时长int[]dp=newint[len];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(inti=2;i 「状态」和「状态转移方程」得到以后，这个问题其实就得到了解决，剩下的一些细节的问题在编码的时候只要稍微留意一点就行了。 方法一：设计二维状态变量第1步：设计状态「状态」这个词可以理解为「记录了求解问题到了哪一个阶段」。 由于当前这一天有按摩师有两种选择：（1）接预约；（2）不接预约。但根据题意，今天是否接预约，是受到昨天影响的。为了消除这种影响，我们在状态数组要设置这个维度。 无后效性的理解：1、后面的决策不会影响到前面的决策；2、之前的状态怎么来的并不重要。 个人理解：其实就是前后状态彼此独立互不干扰，即每个状态都能完整的表示当前状态，不受前后状态的干扰。 一般的情况是，只要有约束，就可以增加一个维度消除这种约束带来的影响，再具体一点说，就是把「状态」定义得清楚、准确，「状态转移方程」就容易得到了。 「力扣」的几道股票问题基本都是这个思路，而且设置状态的思想和这道题是完全一致的。 第2步：状态转移方程「状态转移方程」可以理解为「不同阶段之间的联系」。 第3步：考虑初始化从第2天开始，每天的状态值只与前一天有关，因此第1天就只好老老实实算了。好在不难判断：dp[0][0]=0与dp[0][1]=nums[0]； 这里有一种技巧，可以把状态数组多设置一行，这样可以减少对第1天的初始化，这样的代码把第1天的情况考虑了进去，但编码的时候要注意状态数组下标的设置，请见题解最后的「参考代码3」。 第4步：考虑输出由于状态值的定义是前缀性质的，因此最后一天的状态值就考虑了之前所有的天数的情况。按摩师最后一天可以接受预约，也可以不接受预约，取二者最大值。 第5步：考虑是否可以优化空间由于今天只参考昨天的值，可以使用「滚动数组」完成，优化空间以后的代码丢失了一定可读性，也会给编码增加一点点难度，请见题解后的「参考代码4」。 参考代码1： publicclassSolution{publicintmassage(int[]nums){intlen=nums.length;if(len==0){return0;}if(len==1){returnnums[0];}//dp[i][0]：区间[0,i]里接受预约请求，并且下标为i的这一天不接受预约的最大时长//dp[i][1]：区间[0,i]里接受预约请求，并且下标为i的这一天接受预约的最大时长int[][]dp=newint[len][2];dp[0][0]=0;dp[0][1]=nums[0];for(inti=1;i 以上是中规中矩的写法。在这里根据问题本身的特点，状态可以不用设置那么具体，就将题目问的设计成状态（题目：每个预约都可以选择接或不接），状态转移方程依然好写。 「动态规划」其实不是什么特别难懂的东西（只是说思想），只是这一类问题刚接触的时候有点不太适应，并且这类问题容易被包装得很过分，而且没有明显的套路，题型多样，所以学习「动态规划」会有一些些吃力，这没有办法，见多了就好。如果是准备面试，不需要掌握特别复杂的「动态规划」问题（当然前提是你没有在简历上说你是算法竞赛高手）。 「动态规划」告诉了我们另一种求解问题的思路。我们学习编程，习惯了自顶向下求解问题（递归），在自顶向下求解问题的过程中，发现了重复子问题，我们再加上缓存。而「动态规划」告诉我们，其实有一类问题我们可以从一个最简单的情况开始考虑，通过逐步递推，每一步都记住当前问题的答案，得到最终问题的答案，即「动态规划」告诉了我们「自底向上」思考问题的思路。 也就是说「动态规划」告诉我们的新的思路是：不是直接针对问题求解，由于我们找到了这个问题最开始的样子，因此后面在求解的过程中，每一步都可以参考之前的结果（在处理最优化问题的时候，叫「最优子结构」），由于之前的结果有重复计算（「重复子问题」），因此必须记录下来。 这种感觉不同于「记忆化递归」，「记忆化递归」是直接面对问题求解，遇到一个问题解决了以后，就记下来，随时可能面对新问题。而「动态规划」由于我们发现了这个问题「最初」的样子，因此每一步参考的以前的结果都是知道的，就像我们去考试，所有的考题我们都见过，并且已经计算出了答案一样，我们只需要参考以前做题的答案，就能得到这一题的答案，这是「状态转移」。应用「最优子结构」是同一回事，即：综合以前计算的结果，直接得到当前的最优值。 「动态规划」的内涵和外延很丰富，不是几句话和几个问题能够理解清楚的，需要我们做一些经典的问题去慢慢理解它，和掌握「动态规划」问题思考的方向。 Java publicclassSolution{publicintmassage(int[]nums){intlen=nums.length;//dp数组多设置一行，相应地定义就要改变，遍历的一些细节也要相应改变//dp[i][0]：区间[0,i)里接受预约请求，并且下标为i的这一天不接受预约的最大时长//dp[i][1]：区间[0,i)里接受预约请求，并且下标为i的这一天接受预约的最大时长int[][]dp=newint[len+1][2];//注意：外层循环从1到=len，相对dp数组而言，引用到nums数组的时候就要-1for(inti=1;i<=len;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1]=dp[i-1][0]+nums[i-1];}returnMath.max(dp[len][0],dp[len][1]);}}复杂度分析： 在编码的时候，需要注意，只要访问到dp数组的时候，需要对下标%2，等价的写法是&1。 publicclassSolution{publicintmassage(int[]nums){intlen=nums.length;if(len==0){return0;}if(len==1){returnnums[0];}//dp[i&1][0]：区间[0,i]里接受预约请求，并且下标为i的这一天不接受预约的最大时长//dp[i&1][1]：区间[0,i]里接受预约请求，并且下标为i的这一天接受预约的最大时长int[][]dp=newint[2][2];dp[0][0]=0;dp[0][1]=nums[0];for(inti=1;i 在实现上可以在取下标的时候对3取模。 classSolution{publicintmassage(int[]nums){intlen=nums.length;if(len==0){return0;}if(len==1){returnnums[0];}//dp[i%3]：区间[0，i]里接受预约请求的最大时长int[]dp=newint[3];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(inti=2;i 数组是最常用的数据结构之一，现在我们对数组的下标进行特殊处理，使每一次操作仅保留若干有用信息，新的元素不断循环刷新，看上去数组的空间被滚动地利用，此模型我们称其为滚动数组。其主要达到压缩存储的作用，一般常用在DP类题目中。因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减少内存开支。 类比：滚动数组可以想象成我们的显示屏，对于有很多的数字来说，每次只显示对我们有用的、有限的数字，用完（显示完）就向后移动一位，显示的数量不变。这样可以节省很多空间。 滚动数组是常见的一种空间优化方式。 应用是递推算法，动态规划（其实现方式是递推）。 举个栗子： 斐波那契数列是递推的一个最好的例子，它的递推公式是： 也就是说，我们只需要知道n-1和n-2项就能知道第n项，第n项跟前面的所有项都没关系。 所以我们完全可以只开一个长度为3的数组来完成这个过程。 publicintfib(intn){if(n<=1){return1;}int[]d=newint[n];d[0]=1;d[1]=1;for(inti=2;i 但是注意，上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2]，为了节约空间我们可以使用滚动数组的方法 滚动数组模优化做法：这种数组的滚动可以通过模运算实现，需要多大的数组滚动，模就为几。 publicintfib(intn){if(n<=1){return1;}intd[]=newint[3];d[0]=1;d[1]=1;for(inti=2;i 递推关系式：y=f(x)=x1+x2+... 理解： ①、②、③、4、51、②、③、④、5 ①、②、③、4、5②、③、④、5、6 也可以进一步简化成这样， publicintfib(intn){if(n<=1){return1;}intd[]=newint[3];d[0]=1;d[1]=1;for(inti=2;i 有时候，我们的递推关系式并不明确，并不能直接得出某单元格的值，阶段记录表并不能一次性填好值，得多次迭代填表，需要额外使用一层循环，去考虑不同的情况，不断刷新叠加某一层单元格的值。 可以看到下面的dp只有一维数组，但是额外使用了一层循环，去叠加单元格的值。 面对一些如同背包九讲这样的问题，我们可能会需要对选择的结果集进行去重，比如说选择物品1和5与选择物品5和1，其实是一个相同的结果，我们应该对其进行去重处理。 而我们去重的方式很简单，那就是制定选择规则，赋予我们的选择顺序性。 我们一般采用升序顺序性，我们按照升序顺序来选择我们的元素，比如说选择元素1和5，我们就只有这一种选择，没有5和1这种选择，因为我们是按照升序来选择的。 一般这种问题涉及到如何消除排列组合的影响，也就是说，当成一个集合使用。其实如果我们想要使用这种方法不重复、消除排列组合的影响的话，我们可以使其中的选择元素以某种方式顺序排列，这样就能消除重复的影响了。 动态规划问题一般都带有前缀性，像0/1背包问题，它就是一种双前缀性问题，因为不止它的背包容量具有前缀性，它的物品选择也具有前缀性。它的目的就是为了消除排列组合问题的顺序性，也就是说，我们构造了物品选择编号的一种前缀性，我们就可以决定物品从小到大选择的一种顺序性来避免他们的排列组合重复。 因为我们的动态规划具有当前性，我们只能操作当前的选择当前的节点，所以这会给我们带来一种排列组合的问题，比如说1和5还有5和1，这是两种选择了。如果我们希望把他当成一种选择的话，我们就需要消除这种排列组合带来的问题，我们最好的做法就是将当前性与顺序性相结合，我们的选择按某种递增或递减的顺序来决定，这样就可以消除重复的选择。 这种顺序性，我们可以使用以下两种方法来进行实现。 下面我们拿背包问题来举例子：有n个物品和容量为V的背包，第i件物品的体积为c[i]，价值为w[i]。现在的目标是确定要将哪些物体放入背包，以保证在体积不超过背包容量的前提下，背包内的总价值最高？ 顺序多次迭代填表，顾名思义，我们的表格不是一次性就填好，而是经过多次迭代修改，慢慢地填好。(简单易懂又好用！) 使用多重循环，也就是说我们增加一种循环来保证我们的选择的一个顺序性，我们使用外层循环来保证我们选择的编号顺序由小到大（这种方法也就是我所说的多次迭代填表）。其实，原理就是最外层循环固定当前问题，然后匹配不同的子类问题去解决不同的原问题。保证当前问题不会因为排序而重复处理（组合），[1,2]和[2,1]是一种结果。 我们传统方法是，最外层循环固定原问题，然后划分不同的子类问题和不同的当前问题。 原问题=子类问题+当前问题 先选择1进行填表，再选择5进行迭代填表。。。。 for(intc=0;c<4;++c){ //按照编号升序选择4种硬币 intcoin=coins[c]; for(inti=coin;i<=n;++i){ //每选择一种就迭代填表 f[i]=(f[i]+f[i-coin])%MOD; }}或者 for(intc=0;c<4;++c){ //按照编号升序选择4种硬币 intcoin=coins[c]; for(inti=0;i<=n;++i){ //每选择一种就迭代填表 if(i>=coin){ f[i]=(f[i]+f[i-coin])%MOD; } }}顺序二维数组（顺序性）使用顺序二维状态数组，也就是说，我们额外使用一个数组下标来表示我们的选择的编号顺序由小到大，这样我们就可以使用顺序性来消除重复性。 状态定义：dp[i][j]为前i个物品（物品顺序性）中，容量恰好为j时的最大价值。 for(inti=1;i 如果我们把每次可走步数/零钱面额限制为[1,2]，把楼梯高度/总金额限制为3，那么这两道题目就可以抽象成"给定[1,2]，求组合成3的组合数和排列数"。 接下来引出本文的核心两段代码，虽然是Cpp写的，但是都是最基本的语法，对于可能看不懂的地方，我加了注释。 C++ classSolution1{public:intchange(intamount,vector 因此在不看后面的分析之前，你能分辨出哪个Solution是得到排列，哪个Solution是得到组合吗？ 在揭晓答案之前，让我们先分别用DP的方法解决爬楼梯和零钱兑换II的问题。每个解题步骤都按照DP三部曲，a.定义子问题，b.定义状态数组，c.定义状态转移方程。 问题描述如下: 假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？ 这道题目子问题是，problem(i)=sub(i-1)+sub(i-2),即求解第i阶楼梯等于求解第i-1阶楼梯和第i-2阶楼梯之和。 状态数组是DP[i],状态转移方程是DP[i]=DP[i-1]=DP[i-2] 那么代码也就可以写出来了。 如果我们把问题泛化，不再是固定的1，2，而是任意给定台阶数，例如1,2,5呢？ 我们只需要修改我们的DP方程DP[i]=DP[i-1]+DP[i-2]+DP[i-5],也就是DP[i]=DP[i]+DP[i-j],j=1,2,5 在原来的基础上，我们的代码可以做这样子修改 classSolution{public:intclimbStairs(intn){intDP[n+1];memset(DP,0,sizeof(DP));DP[0]=1;intsteps[2]={1,2};for(inti=1;i<=n;i++){for(intj=0;j<2;j++){intstep=steps[j];if(i 那么这个代码是不是看起来很眼熟呢？我们能不能交换内外的循环呢？也就是下面的代码 for(intj=0;j<2;j++){intstep=steps[j];for(inti=1;i<=n;i++){if(i 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。定义子问题:problem(i)=sum(problem(i-j)),j=1,2,5。含义为凑成总金额i的硬币组合数等于凑成总金额硬币i-1,i-2,i-5,...的子问题之和。 我们发现这个子问题定义居然和我们之前泛化的爬楼梯问题居然是一样的，那后面的状态数组和状态转移方程也是一样的，所以当前问题的代码可以在之前的泛化爬楼梯问题中进行修改而得。 classSolution{public:intchange(intamount,vector 但是当你运行之后，却发现这个代码并不正确，得到的结果比预期的大。究其原因，该代码计算的结果是排列数，而不是组合数，也就是代码会把1,2和2,1当做两种情况。但更加根本的原因是我们子问题定义出现了错误。 正确的子问题定义应该是，problem(k,i)=problem(k-1,i)+problem(k,i-k) 即前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点，那就是用前k的硬币凑齐金额i，要分为两种情况开率，一种是没有用前k-1个硬币就凑齐了，一种是前面已经凑到了i-k，现在就差第k个硬币了。 状态数组就是DP[k][i],即前k个硬币凑齐金额i的组合数。 这里不再是一维数组，而是二维数组。第一个维度用于记录当前组合有没有用到硬币k，第二个维度记录现在凑的金额是多少？如果没有第一个维度信息，当我们凑到金额i的时候，我们不知道之前有没有用到硬币k。 因为这是个组合问题，我们不关心硬币使用的顺序，而是关心硬币有没有被用到。是否使用第k个硬币受到之前情况的影响。 状态转移方程如下 bash if金额数大于硬币DP[k][i]=DP[k-1][i]+DP[k][i-k]elseDP[k][i]=DP[k-1][i]因此正确代码如下: classSolution{public:intchange(intamount,vector 此时，交换这里面的循环不会影响最终的结果。也就是 for(inti=1;i<=amount;i++){for(intk=1;k<=coins.size();k++){if(i>=coins[k-1]){DP[k][i]=DP[k][i-coins[k-1]]+DP[k-1][i];}else{DP[k][i]=DP[k-1][k];}}}之前爬楼梯问题中，我们将一维数组降维成点。这里问题能不能也试着降低一个维度，只用一个数组进行表示呢？ 这个时候，我们就需要重新定义我们的子问题了。 此时的子问题是，对于硬币从0到k，我们必须使用第k个硬币的时候，当前金额的组合数。 因此状态数组DP[i]表示的是对于第k个硬币能凑的组合数 DP[[i]=DP[i]+DP[i-k]于是得到我们开头的第二个Solution。 classSolution{public:intchange(intamount,vector 显然不能，因为我们这里定义的子问题是，必须选择第k个硬币时，凑成金额i的方案。如果交换了，我们的子问题就变了，那就是对于金额i,我们选择硬币的方案。 同样的，我们回答之前爬楼梯的留下的问题，原循环结构对应的子问题是，对于楼梯数i,我们的爬楼梯方案。第二种循环结构则是，固定爬楼梯的顺序，我们爬楼梯的方案。也就是第一种循环下，对于楼梯3，你可以先2再1，或者先1再2，但是对于第二种循环，只能先1再2，有顺序性，只能记录组合数。 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007) 示例1: 输入:n=5输出：2解释:有两种方式可以凑成总金额:5=55=1+1+1+1+1示例2: 输入:n=10输出：4解释:有四种方式可以凑成总金额:10=1010=5+510=5+1+1+1+1+110=1+1+1+1+1+1+1+1+1+1未去重错误答案classSolution{publicintwaysToChange(intn){//动态规划if(n<=1){return1;}int[]dp=newint[n+1];dp[0]=1;for(inti=1;i 前面5种情况数：dp[1,5]=[1,1,1,1,2];coin=1:dp[6]+=(dp[6-coin]=>dp[5]=>2);即拿到coin(1)的情况有两种: coin(1,1,1,1,1)+coin(1); coin(5)+coin(1); coin=5:dp[6]+=(dp[6-coin]=>dp[1]=>1);即拿到coin（5）的情况有一种: coin(1)+coin(5);但是事实却是6的情况只有两种，（1，1，1，1，1，1）和（1，5）。这里是把（1，5）和（5，1）前后顺序不同的情况重复算了1次。因此我们应该去考虑硬币顺序带来的影响。 上面的错误方法我们可以知道，我们应该去消除硬币顺序带来的排列组合的影响。 我们规定硬币编号升序，采用循环顺序多次迭代填表。 classSolution{publicintwaysToChange(intn){//动态规划if(n<=1){return1;}int[]dp=newint[n+1];dp[0]=1;//使用顺序性来消除排列组合带来的重复性，使我们的结果集选择唯一（按硬币选择从小到大排列） //先放1进行填表的情况for(inti=1;i classSolution{publicintwaysToChange(intn){int[]dp=newint[n+1];int[]coins=newint[]{1,5,10,25};//刚好可以用一个硬币凑成的情况，是一种情况//whilei==coin://dp[i]=dp[i-coin]=>dp[0]dp[0]=1;/***dp方程：dp[i]+=dp[i-coin];*/for(intcoin:coins){for(inti=coin;i<=n;i++){dp[i]=(dp[i]+dp[i-coin])%1000000007;}}returndp[n];}}顺序二维数组我们使用顺序二维数组， 状态定义：dp[i][v]为前i个硬币中，金额恰好为v时的表示法个数。 我们使用这个i，前i个物品，来让我们的结果集升序顺序排列。 前i个物品的区间范围，可分为两种情况： 二维数组多次迭代填表： classSolution{publicintwaysToChange(intn){int[]coins={1,5,10,25};int[][]dp=newint[4][n+1];//初始化for(inti=0;i 答案需要取模1e9+7（1000000007），如计算初始结果为：1000000008，请返回1。 输入：n=2输出：2示例2： 输入：n=7输出：21示例3： 输入：n=0输出：1我的classSolution{publicintnumWays(intn){if(n<=1){return1;}int[]dp=newint[n+1];dp[0]=1;dp[1]=1;dp[2]=2;for(inti=3;i 例如：输入台阶数：3输出种类数：4解释：4种跳法分别是(1,1,1),(1,2),(2,1),(3) 这里我是运用了“数学”来得出式子的，为了告诉大家不要拘泥于程序，数学也是一个很有用的工具。 用Fib(n)表示超级青蛙跳上n阶台阶的跳法数。如果按照定义，Fib(0)肯定需要为0，否则没有意义。我们设定Fib(0)=1；n=0是特殊情况，通过下面的分析会知道，令Fib(0)=1很有好处。 PS：Fib(0)等于几都不影响我们解题，但是会影响我们下面的分析理解。 当n=1时，只有一种跳法，即1阶跳：\(Fib(1)=1\); 当n=2时，有两种跳的方式，一阶跳和二阶跳：\(Fib(2)=2\);到这里为止，和普通跳台阶是一样的。 当n=3时，有三种跳的方式，第一次跳出一阶后，对应Fib(3-1)种跳法；第一次跳出二阶后，对应Fib(3-2)种跳法；第一次跳出三阶后，只有这一种跳法。 通过上述分析，我们就得到了数列通项公式： 因此，有$$Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+...+Fib(n-2)$$两式相减得：$$Fib(n)-Fib(n-1)=Fib(n-1)$$$$Fib(n)=2Fib(n-1),n>=3$$这就是我们需要的递推公式：$$Fib(n)=2Fib(n-1),n>=3$$ 圆环上有10个点，编号0~9。从0出发，每次可以顺时针或逆时针走一格，请问一共走且仅走n步回到原点的方法有多少种。 数据范围：\(1\len\le10^4\)，由于答案可能会非常大，所以请对答案对\(10^9+7\)取模 示例1 输入：3返回值：0说明：无论如何也不可能走3步回到原点示例2 输入：2返回值：2说明：可能的方案有0->1->0，0->9->0答案走n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数。 这里需要注意，Java中的%代表取余运算，而非取模运算，对正数来说取模和取余是相同的结果，但是对负数来说，取模会得到正数，取余会得到负数。-1%10==-1所以我们需要对负数加上模，变成正数，才能正常取模。 问总共有多少条不同的路径？ 这里为了让大家能明白历史记录表的作用，我举了一道二维表的题。 由题可知，我们的目的是从左上角到右下角一共有多少种路径。那我们就定义dp[i][j]的含义为：当机器人从左上角走到(i,j)这个位置时，一共有dp[i][j]种路径。那么dp[m-1][n-1]就是我们要找的答案了。 由于明确了数组的含义，我们可以知道这其实是一张二维表。 这时，看题目的要求限制：机器人每次只能向下或者向右移动一步。所以我们从左上角开始，向下的那一列（即第一列）和向右的那一行（即第一行）上面所有的节点，都只有一条路径到那。因此，初始值如下： 这是动态规划四步走中最难的一步，我们从dp[i][j]=这一数学公式开始推想。 由于机器人只能向下走或者向右走，所以有两种方式到达(i,j)： 所以我们可以知道，到达(i,j)的所有路径为这两种方式的和，可以得出递推关系式：dp[i][j]=dp[i-1,j]+dp[i,j-1] 我们可以利用此递推关系式，写出程序填完整个表项。在下面代码中，我选择的是逐行填入表格。 publicstaticintuniquePaths(intm,intn){ if(m<=0||n<=0){ return0; } int[][]dp=newint[m][n]; //地图 //初始化 for(inti=0;i 为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8 答案：做到这里，大家应该对动态规划很熟悉了，那么我们就加快速度。 一眼望去，我们这里的状态需要三个变量来存储： 所以我们采用二维数组的方法来存取。 状态：v[i][j]代表当前背包容量j，前i个物品最佳组合对应的价值 寻找递推关系式，面对当前商品有两种可能性： 其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i)表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)； 由此可以得出递推关系式： 可以这么理解，如果要到达V(i,j)这一个状态有几种方式？ 肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。 然后一行一行的填表： 如，i=1，j=1，w(1)=2，v(1)=3，有j 表格填完可知，最优解即是V(number,capacity)=V(4,8)=10。 #include 就拿上面的例子来说吧： 代码实现背包问题最终版详细代码实现如下： 注意，这里不能使用滚动数组，因为我们的代码bag[i][j]=Math.max(bag[i-1][j],bag[i-1][j-w[i]]+v[i]);有较大的跳跃性。 那么，我们试试看用自己的方法做一下！ 我们的状态需要三个变量来存储，所以我们采用二维数组dp[i][j]=k;： i取决于状态个数，即模式串pat的字符个数+1 只有遇到匹配的字符我们的状态0才能前进为状态1，遇到其它字符的话还是停留在状态0。 这一步是最难的，我们怎么递推呢？ 我们可以把状态的操作分为前进和后退两个部分 所谓影子状态，就是和当前状态具有相同前缀的状态。就是用来方便回溯的，作为当前状态j的一种“特殊的”前驱结点，即X->j 这个倒退过程，其实就是后缀覆盖前缀的过程。 箭头A(状态X)箭头B(状态X+1)：dp[X][B]就代表有AB前缀的状态 (状态X)箭头B：这种组合是一体的，谁也离不开谁。 那么我们的X从哪里来呢？ 详情可以看看下面代码的注释，在这里就不过多解释了。 输入:[7,1,5,3,6,4]输出:5解释:在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1=5。注意利润不能是7-1=6,因为卖出价格需要大于买入价格。示例2: 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。 输入：[7,1,5,3,6,4]输出：5解释：在第2天（股票价格=1）的时候买入，在第5天（股票价格=6）的时候卖出，最大利润=6-1=5。注意利润不能是7-1=6,因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例2： 输入：prices=[7,6,4,3,1]输出：0解释：在这种情况下,没有交易完成,所以最大利润为0。答案一次遍历算法 假设给定的数组为：[7,1,5,3,6,4] 显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格minprice，我们就可以假设自己的股票是在那天买的。那么我们在第i天卖出股票能得到的利润就是prices[i]-minprice。 因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。 publicclassSolution{publicintmaxProfit(intprices[]){intminprice=Integer.MAX_VALUE;intmaxprofit=0;for(inti=0;i 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 输入:[7,1,5,3,6,4]输出:7解释:在第2天（股票价格=1）的时候买入，在第3天（股票价格=5）的时候卖出,这笔交易所能获得利润=5-1=4。随后，在第4天（股票价格=3）的时候买入，在第5天（股票价格=6）的时候卖出,这笔交易所能获得利润=6-3=3。示例2: 输入:[1,2,3,4,5]输出:4解释:在第1天（股票价格=1）的时候买入，在第5天（股票价格=5）的时候卖出,这笔交易所能获得利润=5-1=4。注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例3: 输入:[7,6,4,3,1]输出:0解释:在这种情况下,没有交易完成,所以最大利润为0。答案与Ⅰ不同，这题不限制买卖次数，Ⅰ只能买卖一次。 需要设置一个二维矩阵表示状态。 第1步：定义状态状态dp[i][j]定义如下： dp[i][j]表示到下标为i的这一天，持股状态为j时，我们手上拥有的最大现金数。 注意：限定持股状态为j是为了方便推导状态转移方程，这样的做法满足无后效性。 其中： 第2步：思考状态转移方程状态从持有现金（cash）开始，到最后一天我们关心的状态依然是持有现金（cash）；每一天状态可以转移，也可以不动。状态转移用下图表示： 说明： 第3步：确定初始值起始的时候： 第4步：确定输出值终止的时候，上面也分析了，输出dp[len-1][0]，因为一定有dp[len-1][0]>dp[len-1][1]。 classSolution{publicintmaxProfit(int[]prices){intn=prices.length;int[][]dp=newint[n][2];dp[0][0]=0;dp[0][1]=-prices[0];for(inti=1;i 设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。 输入：prices=[3,3,5,0,0,3,1,4]输出：6解释：在第4天（股票价格=0）的时候买入，在第6天（股票价格=3）的时候卖出，这笔交易所能获得利润=3-0=3。随后，在第7天（股票价格=1）的时候买入，在第8天（股票价格=4）的时候卖出，这笔交易所能获得利润=4-1=3。示例2： 输入：prices=[1,2,3,4,5]输出：4解释：在第1天（股票价格=1）的时候买入，在第5天（股票价格=5）的时候卖出,这笔交易所能获得利润=5-1=4。注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。示例3： 输入：prices=[7,6,4,3,1]输出：0解释：在这个情况下,没有交易完成,所以最大利润为0。示例4： 输入：prices=[1]输出：0答案一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过 所以定义状态转移数组dp[天数][当前是否持股][卖出的次数] 具体一天结束时的6种状态： 根据这些状态即可轻松写出代码 技巧：因为最小值再减去1就是最大值（越界了）Integer.MIN_VALUE-1=Integer.MAX_VALUE，所以采用intMIN_VALUE=Integer.MIN_VALUE/2; 设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。 输入：k=2,prices=[2,4,1]输出：2解释：在第1天(股票价格=2)的时候买入，在第2天(股票价格=4)的时候卖出，这笔交易所能获得利润=4-2=2。示例2： 输入：k=2,prices=[3,2,6,5,0,3]输出：7解释：在第2天(股票价格=2)的时候买入，在第3天(股票价格=6)的时候卖出,这笔交易所能获得利润=6-2=4。随后，在第5天(股票价格=0)的时候买入，在第6天(股票价格=3)的时候卖出,这笔交易所能获得利润=3-0=3。我的在Ⅲ的基础上进行扩充，可以看到我们的状态数组变成三维了，初始化范围变得不太容易确定了。 我们可以通过递推关系式，数组下标的越界，来确定我们的初始化范围 输入:12258输出:5解释:12258有5种不同的翻译，分别是"bccfi","bwfi","bczi","mcfi"和"mzi"动态规划答案我们可以看出它的递推范围为2，即我们的1位字符和2位字符都有可能被翻译。 所以我们要找的递推关系式为：dp[n]=dp[n-1]+dp[n-2]（这个n-2不一定能成立。。） classSolution{publicinttranslateNum(intnum){//回溯法思想：循环层数不确定//一个得算//1个两个得算//2个两个得算//3个两个。。。。//动态规划思想：数字位数n的阶段，数字位数n-1、n-2的阶段，能不能推出来Stringstr=String.valueOf(num);//状态：前n位数，翻译方法数int[]dp=newint[str.length()+1];//初始化，一位数dp[0]=1;dp[1]=1;for(inti=2;i 回溯法分析，存在两个分支： 你需要用一个浮点数数组返回答案，其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。 输入:1输出:[0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例2: 输入:2输出:1解释:2=1+1,1×1=1示例2: 输入:10输出:36解释:10=3+3+4,3×3×4=36答案动态规划，自底向上，我们从绳长为2开始看起，慢慢把绳长+1，看看是否可以借助前一个结果来达成目的 输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大，为6。答案动态规划解析： 为何定义最大和dp[i]中必须包含元素nums[i]：保证dp[i]递推到dp[i+1]的正确性；如果不包含nums[i]，递推时则不满足题目的连续子数组要求。 转移方程：若\(dp[i-1]\leq0\)，说明dp[i-1]对dp[i]产生负贡献，即dp[i-1]+nums[i]还不如nums[i]本身大。 初始状态：dp[0]=nums[0]，即以nums[0]结尾的连续子数组最大和为nums[0]。 返回值：返回dp列表中的最大值，代表全局最大值。 原问题：[1,2,3,4]的最大和子类问题：[1,2,3]的最大和当前问题：4 输入:"abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc"，所以其长度为3。示例2: 输入:"bbbbb"输出:1解释:因为无重复字符的最长子串是"b"，所以其长度为1。示例3: 输入:"pwwkew"输出:3解释:因为无重复字符的最长子串是"wke"，所以其长度为3。请注意，你的答案必须是子串的长度，"pwke"是一个子序列，不是子串。动态规划这题本来是用滑动窗口做的，但是这里，动态规划也可以做 动态规划+哈希表 状态定义：设动态规划列表dp，dp[j]代表以字符s[j]为结尾的“最长不重复子字符串”的长度。 转移方程：固定右边界j，设字符s[j]左边距离最近的相同字符为s[i]，即s[i]=s[j]。 当i<0时，由于dp[j1]≤j恒成立，因而dp[j-1] 返回值：max(dp)，即全局的“最长不重复子字符串”的长度。 哈希表统计：遍历字符串s时，使用哈希表（记为map）统计各字符最后一次出现的索引位置。左边界i获取方式：遍历到s[j]时，可通过访问哈希表map[s[j]]获取最近的相同字符的索引i。 原问题：abca子类问题：abc，长度3当前问题：a classSolution{publicintlengthOfLongestSubstring(Strings){if(s.length()<=1){returns.length();}char[]chars=s.toCharArray();//存放元素和其对应下标Map 有2*n的一个长方形方格，用一个1*2的骨牌铺满方格编写一个程序，试对给出的任意一个n(n>0),输出铺法总数。 【算法分析】（1）当n=1时，只能是一种铺法，铺法总数有示为x1=1。（2）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为x2=2； 推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑，只有这两种可能，所以有：f(n)=f(n-1)+f(n-2)（n>2）f(1)=1f(2)=2【代码】 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。 你可以认为每种硬币的数量是无限的。 输入：coins=[1,2,5],amount=11输出：3解释：11=5+5+1示例2： 输入：coins=[2],amount=3输出：-1示例3： 输入：coins=[1],amount=0输出：0我的以总价值的增减进行递推 classSolution{publicintcoinChange(int[]coins,intamount){intmax=amount+1;int[]dp=newint[amount+1];Arrays.fill(dp,max); //初始化dp[0]=0;for(intcoin:coins){if(coin<=amount){dp[coin]=1;}}for(inti=1;i<=amount;i++){ //按总金额的增减进行递推for(intj=0;j<=i/2;j++){dp[i]=Math.min(dp[j]+dp[i-j],dp[i]);}}returndp[amount]==max-1:dp[amount];}}答案我们采用自下而上的方式进行思考。仍定义F(i)为组成金额i所需最少的硬币数量，假设在计算F(i)之前，我们已经计算出F(0)F(i1)的答案。则F(i)对应的转移方程应为 其中\(c_j\)代表的是第j枚硬币的面值，即我们枚举最后一枚硬币面额是\(c_j\)，那么需要从\(i-c_j\)这个金额的状态\(F(i-c_j)\)转移过来，再算上枚举的这枚硬币数量1的贡献，由于要硬币数量最少，所以F(i)为前面能转移过来的状态的最小值加上枚举的硬币数量1。 例子1：假设 coins=[1,2,5],amount=11则，当i==0时无法用硬币组成，为0。当i<0时，忽略F(i) 我们可以看到问题的答案是通过子问题的最优解得到的。 例子2：假设 在上图中，可以看到： publicclassSolution{publicintcoinChange(int[]coins,intamount){intmax=amount+1; //dp数组的含义为总金额为i的情况下，所需最少硬币个数int[]dp=newint[amount+1]; Arrays.fill(dp,max); //初始化dp[0]=0; for(inti=1;i<=amount;i++){ //按单个硬币的增减进行递推for(intj=0;j 给你一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0。 假设每一种面额的硬币有无限个。 题目数据保证结果符合32位带符号整数。 输入：amount=5,coins=[1,2,5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1示例2： 输入：amount=3,coins=[2]输出：0解释：只用面额2的硬币不能凑成总金额3。示例3： 输入：amount=10,coins=[10]输出：1动态规划这道题中，给定总金额amount和数组coins，要求计算金额之和等于amount的硬币组合数。其中，coins的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。 可以通过动态规划的方法计算可能的组合数。用dp[x]表示金额之和等于x的硬币组合数，目标是求dp[amount]。 动态规划的边界是dp[0]=1。只有当不选取任何硬币时，金额之和才为0，因此只有1种硬币组合。 对于面额为coin的硬币，当coin≤i≤amount时，如果存在一种硬币组合的金额之和等于icoin，则在该硬币组合中增加一个面额为coin的硬币，即可得到一种金额之和等于i的硬币组合。因此需要遍历coins，对于其中的每一种面额的硬币，更新数组dp中的每个大于或等于该面额的元素的值。 由此可以得到动态规划的做法： 上述做法不会重复计算不同的排列。因为外层循环是遍历数组coins的值，内层循环是遍历不同的金额之和，在计算dp[i]的值时，可以确保金额之和等于i的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。 例如，coins=[1,2]，对于dp[3]的计算，一定是先遍历硬币面额1后遍历硬币面额2，只会出现以下2种组合： 硬币面额2不可能出现在硬币面额1之前，即不会重复计算3=2+1的情况。 classSolution{publicintchange(intamount,int[]coins){int[]dp=newint[amount+1];dp[0]=1; //固定当前问题for(intcoin:coins){for(inti=coin;i<=amount;i++){dp[i]+=dp[i-coin];}}returndp[amount];}}复杂度分析 空间复杂度：\(O(\textit{amount})\)，其中amount是总金额。需要创建长度为amount+1的数组dp。 给你一个整数数组nums，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。 输入：nums=[10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是[2,3,7,101]，因此长度为4。示例2： 输入：nums=[0,1,0,3,2,3]输出：4示例3： 输入：nums=[7,7,7,7,7,7,7]输出：1我的如果不选用确定的尾元素，那我们对当前节点的状态将会一无所知，无法进行递推。 子类问题需要多次填表，需要额外的一层循环 classSolution{publicintlengthOfLIS(int[]nums){intres=1;int[]dp=newint[nums.length]; //这里没有先进行初始化是因为递推公式没有任何限制，可以直接递推//Arrays.fill(dp,1);for(inti=0;i 空间复杂度：\(O(n)\)，需要额外使用长度为n的dp数组。 思路与算法 考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。 基于上面的贪心思路，我们维护一个数组d[i]，表示长度为i的最长上升子序列的末尾元素的最小值，用len记录目前最长上升子序列的长度，起始时len为1，\(d[1]=\textit{nums}[0]\)。 同时我们可以注意到d[i]是关于i单调递增的。因为如果\(d[j]\geqd[i]\)且j 我们依次遍历数组nums中的每个元素，并更新数组d和len的值。如果\(\textit{nums}[i]>d[\textit{len}]\)则更新\(len=len+1\)，否则在\(d[1\ldotslen]\)中找满足\(d[i-1]<\textit{nums}[j] 最后整个算法流程为： 设当前已求出的最长上升子序列的长度为len（初始时为1），从前往后遍历数组nums，在遍历到nums[i]时： 如果\(\textit{nums}[i]>d[\textit{len}]\)，则直接加入到d数组末尾，并更新\(\textit{len}=\textit{len}+1\)； 否则，在d数组中二分查找，找到第一个比nums[i]小的数d[k]，并更新\(d[k+1]=\textit{nums}[i]\)。 以输入序列[0,8,4,12,2]为例： 第一步插入0，d=[0]； 第二步插入8，d=[0,8]； 第三步插入4，d=[0,4]； 第四步插入12，d=[0,4,12]； 第五步插入2，d=[0,2,12]。 最终得到最大递增子序列长度为3。 classSolution{publicintlengthOfLIS(int[]nums){intlen=1,n=nums.length;if(n==0){return0;}int[]d=newint[n+1];d[len]=nums[0];for(inti=1;i 空间复杂度：\(O(n)\)，需要额外使用长度为n的d数组。 给定一个字符串s和一个字符串t，计算在s的子序列中t出现的个数。 字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是） 题目数据保证答案符合32位带符号整数范围。 输入：s="rabbbit",t="rabbit"输出：3解释：如下图所示,有3种可以从s中得到"rabbit"的方案。rabbbitrabbbitrabbbit示例2： 输入：s="babgbag",t="bag"输出：5解释：如下图所示,有5种可以从s中得到"bag"的方案。babgbagbabgbagbabgbagbabgbagbabgbag双重线性动态规划可以看到这题不光有一个原问题babgbag，还有一个原问题bag。这两个原问题都需要划分子类问题，才能够进行求解。所以说是双重线性动态规划。 动态规划 dp[i][j]代表T的前i字符串可以由S的前j字符串组成最多个数. 所以动态方程: 当S[j]==T[i],dp[i][j]=dp[i-1][j-1]+dp[i][j-1]; 当S[j]!=T[i],dp[i][j]=dp[i][j-1] 对于第一行,T为空,因为空集是所有字符串子集,所以我们第一行都是1 对于第一列,S为空,这样组成T个数当然为0了 至于下面如何进行,大家可以通过动态方程,自行模拟一下! 代码: 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。 输入：text1="abcde",text2="ace"输出：3解释：最长公共子序列是"ace"，它的长度为3。示例2： 输入：text1="abc",text2="abc"输出：3解释：最长公共子序列是"abc"，它的长度为3。示例3： 输入：text1="abc",text2="def"输出：0解释：两个字符串没有公共子序列，返回0。答案已知text1、text2，两个线性问题 classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intM=text1.length();intN=text2.length();int[][]dp=newint[M+1][N+1];for(inti=1;i<=M;++i){for(intj=1;j<=N;++j){//dp[i][j]=dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]if(text1.charAt(i-1)==text2.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[M][N];}}数组为boolean实例boolean代表着某种结果的可行性。 给你一个字符串s，找到s中最长的回文子串。 输入：s="babad"输出："bab"解释："aba"同样是符合题意的答案。示例2： 输入：s="cbbd"输出："bb"动态规划思路与算法 对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串“ababa”，如果我们已经知道“bab”是回文串，那么“ababa”一定是回文串，这是因为它的首尾两个字母都是“a”。 根据这样的思路，我们就可以用动态规划的方法解决本题。我们用P(i,j)表示字符串s的第i到j个字母组成的串（下文表示成s[i:j]）是否为回文串： 回文串： 这里的「其它情况」包含两种可能性： s[i,j]本身不是一个回文串； i>j，此时s[i,j]本身不合法。 那么我们就可以写出动态规划的状态转移方程： 也就是说，只有s[i+1:j1]是回文串，并且s的第i和j个字母相同时，s[i:j]才会是回文串。 上文的所有讨论是建立在子串长度大于2的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为1或2。对于长度为1的子串，它显然是个回文串；对于长度为2的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件： 动态规划的边界条件： 根据这个思路，我们就可以完成动态规划了，最终的答案即为所有\(P(i,j)=\text{true}\)中ji+1（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。 原问题：abcdcba子类问题：bcdcb当前问题：左a和右a publicclassSolution{publicStringlongestPalindrome(Strings){intlen=s.length();char[]chars=s.toCharArray();intresLeft=0,resRight=0;//dp[i][j]表示s[i..j]是否是回文串boolean[][]dp=newboolean[len][len];//初始化：所有长度为1的子串都是回文串for(inti=0;i 原问题：dp[left][right]子类问题：dp[left+1][right-1] 也就是说，窗口长度为1和2的都可能需要初始化 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 输入:s="leetcode",wordDict=["leet","code"]输出:true解释:返回true因为"leetcode"可以由"leet"和"code"拼接成。示例2： 输入:s="applepenapple",wordDict=["apple","pen"]输出:true解释:返回true因为"applepenapple"可以由"apple""pen""apple"拼接成。注意，你可以重复使用字典中的单词。示例3： 输入:s="catsandog",wordDict=["cats","dog","sand","and","cat"]输出:false我的分析方法分析：当然，这题也可以使用字典树来做！ 原问题：leetcode是否可被拼接出（原问题=子类问题+当前问题）子类问题：子类问题不止于后面的一个元素有关，需要重新遍历前面所有的问题。 最小问题：空字符串 输入：nums=[1,5,11,5]输出：true解释：数组可以分割成[1,5,5]和[11]。示例2： 输入：nums=[1,2,3,5]输出：false解释：数组不能分割成两个元素和相等的子集。我的回溯（最优解）很遗憾回溯法超时了，但是如果题目问的是这两个子集分别是什么（华为笔试），那回溯法就是很好的一个方法。 classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums){sum+=num;}if(sum%2==1){returnfalse;}sum=sum/2;//从集合中找出和为sum的子数组boolean[][]dp=newboolean[nums.length][sum+1];for(inti=0;i 现在我们已知小数组的和，我们希望在大数组中挑选出子集元素，子集元素的和组合成小数组的和。 我们来举个例子吧： 所以我们的dp数组，需要记录 需要二维dp数组，booleandp[i][j]代表0~i数组中子集的和为j是否可行 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 输入：nums=[2,3,1,1,4]输出：true解释：可以先跳1步，从下标0到达下标1,然后再从下标1跳3步到达最后一个下标。示例2： 输入：nums=[3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为3的位置。但该下标的最大跳跃长度是0，所以永远不可能到达最后一个下标。我的动态规划dp数组来记录下当前第i个元素是否可达，迭代多次填表。 classSolution{publicbooleancanJump(int[]nums){//dp[i]，从0跳到位置i时的最少跳跃次数boolean[]dp=newboolean[nums.length]; //因为下面会+1，超出了边界，所以除以2dp[0]=true;for(inti=0;i 原问题：dp[i]可达的最远距离子类问题：dp[0..i-1]可达的最远距离当前问题： 后来发现，只用通过一个元素记录最远距离即可。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 输入:nums=[2,3,1,1,4]输出:2解释:跳到最后一个位置的最小跳跃数是2。从下标为0跳到下标为1的位置，跳1步，然后跳3步到达数组的最后一个位置。示例2: 输入:nums=[2,3,0,1,4]输出:2动态规划用动态规划多次填表，dp[i]，从0跳到位置i时的最少跳跃次数。从前往后遍历，多次填表。 由于子类问题和当前问题不唯一，所以需要两个for循环。 例如，对于数组[2,3,1,2,4,2,3]，初始位置是下标0，从下标0出发，最远可到达下标2。下标0可到达的位置中，下标1的值是3，从下标1出发可以达到更远的位置，因此第一步到达下标1。 从下标1出发，最远可到达下标4。下标1可到达的位置中，下标4的值是4，从下标4出发可以达到更远的位置，因此第二步到达下标4。 在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加1。 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。 classSolution{publicintjump(int[]nums){intlength=nums.length;intend=0; //结束位置intmaxPosition=0; //最大位置intsteps=0;for(inti=0;i 多数组动态规划，其实也可以视作多维的动态规划数组，只不过这维度保存的状态可能填表顺序不一样，就拿[接雨水]这题来说，我们需要两个动态规划数组，一个存放左边的最大值，从左往右填表，一个存放右边的最大值，从右往左填表。 给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个32-位整数。 子数组是数组的连续子序列。 输入:nums=[2,3,-2,4]输出:6解释:子数组[2,3]有最大乘积6。示例2: 输入:nums=[-2,0,-1]输出:0解释:结果不能为2,因为[-2,-1]不是子数组。多数组动态规划因为有负数存在，最小值也可以变成最大值，所以需要小心了，需要两个动态规划数组来分别存放当前最大值和当前最小值。 输入：height=[0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）。示例2： 输入：height=[4,2,0,3,2,5]输出：9多数组动态规划虽然这题我用双指针做的，但是也不妨碍有动态规划的方法。 对于下标i，下雨后水能到达的最大高度等于下标i两边的最大高度的最小值，下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]。 创建两个长度为n的数组leftMax和rightMax。对于\(0≤i 显然，\(leftMax[0]=height[0]\)，\([n-1]rightMax[n1]=height[n1]\)。两个数组的其余元素的计算如下： 因此可以正向遍历数组height得到数组leftMax的每个元素值，反向遍历数组height得到数组\textit{rightMax}ightMax的每个元素值。 在得到数组\(leftMax\)和\(rightMax\)的每个元素值之后，对于\(0≤i 多数组：左当前最大值、右当前最大值 从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上） 现在当倾倒了非负整数杯香槟后，返回第i行j个玻璃杯所盛放的香槟占玻璃杯容积的比例（i和j都从0开始）。 输入:poured(倾倒香槟总杯数)=1,query_glass(杯子的位置数)=1,query_row(行数)=1输出:0.00000解释:我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。示例2: 输入:poured(倾倒香槟总杯数)=2,query_glass(杯子的位置数)=1,query_row(行数)=1输出:0.50000解释:我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。示例3: 输入:poured=100000009,query_row=33,query_glass=17输出:1.00000我的原问题：dp[i][j]第i行第j列有多少水流进子类问题：dp[i-1][j-1]和dp[i-1][j]有多少水流进去当前问题：杯子装满之后会进行分流，有一半的水会流到当前杯子 输入：matrix=[["0","1"],["1","0"]]输出：1示例3： 输入：matrix=[["0"]]输出：0方法一：暴力法由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。 暴力法是最简单直观的做法，具体做法如下： 遍历矩阵中的每个元素，每次遇到1，则将该元素作为正方形的左上角； 确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含1的最大正方形； 每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是1。 classSolution{publicintmaximalSquare(char[][]matrix){intmaxSide=0;if(matrix==null||matrix.length==0||matrix[0].length==0){returnmaxSide;}introws=matrix.length,columns=matrix[0].length;for(inti=0;i 那么如何计算dp中的每个元素值呢？对于每个位置(i,j)，检查在矩阵中该位置的值： 如果该位置的值是0，则dp(i,j)=0，因为当前位置不可能在由1组成的正方形中； 如果该位置的值是1，则dp(i,j)的值由其上方、左方和左上方的三个相邻位置的dp值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加1，状态转移方程如下： 此外，还需要考虑边界条件。如果i和j中至少有一个为0，则以位置(i,j)为右下角的最大正方形的边长只能是1，因此dp(i,j)=1。 以下用一个例子具体说明。原始矩阵如下。 0111011110011110111100111对应的dp值如下。 classSolution{publicintmaximalSquare(char[][]matrix){intmaxSide=0;if(matrix==null||matrix.length==0||matrix[0].length==0){returnmaxSide;}introws=matrix.length,columns=matrix[0].length;int[][]dp=newint[rows][columns];for(inti=0;i 空间复杂度：\(O(mn)\)，其中m和n是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵dp。由于状态转移方程中的dp(i,j)由其上方、左方和左上方的三个相邻位置的dp值决定，因此可以使用两个一维数组进行状态转移，空间复杂度优化至\(O(n)\)。 初始化数组的时候记得也要记录最大边！！ classSolution{publicintmaximalSquare(char[][]matrix){intmaxSide=0;if(matrix==null||matrix.length==0||matrix[0].length==0){returnmaxSide;}introws=matrix.length,columns=matrix[0].length;int[][]dp=newint[rows][columns];//初始化for(inti=0;i