此博文是继动态规划总结之后的案例分析

动态规划的代码很简洁，基本在20行以内。

一维状态定义
53 最大子序和
要求元素是连续的！
一般来说，子序列的遍历有三种方式：
1.以某个元素为起始点，形成长度递增的子序列
2.以某个元素为终点，形成长度递增的子序列
3.某序列长度递增，形成子序列，如长度为1的子序列就是原始序列中的所有元素

状态定义：dp[i]为以nums[i]结尾的连续子数组的最大和
状态转移方程：dp[i]=max(dp[i-1] + nums[i], nums[i])
状态初始化：dp[0]=nums[0]
输出：dp[i]中最大元素

139 字符串拆分
按照子串长度增加来遍历字符串的子串
字符串s可以被拆分成子问题 s1 和 s2
指针 i和 j，其中 i 是当前字符串从头开始的子字符串s'的长度，子串以s[i]结尾；
j是当前子字符串s′的拆分位置，拆分成 s'(0,j)和)s′ (j+1,i) 。用下标 i 来考虑所有从当前字符串开始的可能的子字符串。对于每一个子字符串，我们通过下标 j 将它拆分成 s1'′ 和 s2′ （注意 i 现在指向 s2'的结尾）。

状态：dp[i]为从首字符到以s[i]结尾的子串是否可以被空格拆分为多个在字典中出现的单词（i既是长度也是子串末尾的索引）
状态转移方程：dp[i]的转移关系，如果dp[i - j]是true并且s[j:i]在wordDict里, 那么dp[i] = true;（分类讨论）
状态初始化：dp[0]=1，因为空字符串总是字典的一部分
输出：dp[n]

198 打家劫舍
不能偷连续的两家，与之前的2个状态有关

状态：dp[i]为偷到第i家，最大偷窃金额(包含第i家)
状态转移方程：dp[i] = max(dp[i - 2] + nums[i], dp[i-1]);
状态初始化：dp[0]=nums[0], dp[1]=max(nums[0], nums[1]);
输出：dp[n]

264 丑数ii
序列是固定的，关键是如何生成。dp[i]与三个状态有关，之前的数与三个数做乘积，dp保存大小按序排列的丑数，找出下一个丑数。

状态：dp[i]为第i个丑数的值
状态转移方程：dp[i]=min(dp[t2]*2,min(dp[t3]*3,dp[t5]*5))
状态初始化：dp[0]=1,第一个丑数是1
输出：dp[n]

279 完全平方数
对于每个i，它都可以表达为，存在一个j，使得i等于i-jj与jj的和，与所有的状态都有关

状态：dp[i]为组成i的完全平方数的最小个数
状态转移方程：dp[i] = min(dp[i], dp[i - j*j] + 1);
状态初始化：dp[i]=INT_MAX
输出：dp[n]

300 最长上升子序列
dp[i]与之前所有的状态都有关系

状态：dp[i]为以nums[i]为结尾的子序列的最大长度，注意包含nums[i]
状态转移方程：dp[i] = max(dp[i], dp[j] + 1)。在索引 i 之前严格小于 nums[i] 的所有状态中的最大者 + 1，因为这个状态转移与前面所有的状态都有关系，要找到最大的一个状态
初始化：每个字符都是长度为1的子序列
输出：dp中的最大值

322 零钱兑换
完全背包问题，每种物品可以放无限多次。
自底而上和自顶而下两种方法，动态规划是自底而上。当发现最优子结构：对于金额n，减去某个面额m1后，剩下的金额n-m1还需要所有的面额去凑n-m1,从而形成最优子结构。

当前状态与之前若干种状态相关，这些状态通过硬币面额来获得。也是要遍历所有的硬币面额。

纯粹的贪心会出错，因为最先找到的并不一定是最优解，所以还要dfs进行搜索

状态：dp[i]凑成总金额i所需的最小的硬币数
状态转移方程：假如面值是1,2,5，则f(n)=min(f(n-1)+1, f(n-2)+1, f(n-5)+1)
状态初始化：dp所有元素取INT_MAX
输出：dp(n)

338 比特位计数
与数字的奇偶有关。
奇数的二进制中1的个数=它上一位偶数的二进制中1的个数+1
偶数中二进制1的个数等于这个偶数除以2后的数二进制1的个数,因为偶数的2倍相当于左移1位，末尾填0,1的个数不变。
当前状态与之前的某些状态有关，通过奇偶数二进制中含1的个数关系找到相应状态

状态:dp[i]为数字i中含有1的数目
状态转移方程：dp[i]与i的奇偶有关，i为奇数时候，dp[i] = dp[i - 1] + 1;i为偶数时，dp[i] = dp[i / 2];
状态初始化：dp[0]=0
输出：dp[n]

343 整数拆分
状态根据题目问题进行定义，很难一下发现状态转移方程。当前状态与之前的所有状态有关，i拆分为 j 和 i-j，拆分j后dp[i-j]与j不一定谁大，需要比较下，比如2拆分1*1与2相比，i-j就大! 有两层循环，内层循环，遍历之前的状态。

状态：dp[i]为整数i拆分后因数的最大乘积
状态转移方程：dp[i] = max(dp[i], max(dp[i-j], i-j) * j);
状态初始化：dp[0]=0, dp[1]=1;
输出：dp[n]

357 计算各个位数不同的数字个数
数学的排列组合问题，A_n_m，无放回的抽取，注意首位不能为0
可以计算个位，十位，百位，千位的数字，然后所有的数相加
当前状态只与上一个状态有关系

状态：dp[i]为从10^i-1到10^i中有多少个，各个位数不同的数
状态转移方程：dp[i]=dp[i-1]*（11-i）,9*9*8*7*6*5...因为每多一位，就会乘一个数
状态初始化：dp[0]=1;dp[2]=9
输出：dp所有元素之和

368 最大整除子集
子集中，所有元素相互能整除，找到这个最大的子集中的所有的元素，排序后，找到数组中能整除的最长串。
dp[i]也是与之前所有的状态有关，因为nums[i]可能是在前面某个序列的后一个，所以要遍历之前所有的状态
这道题的代码非常tricky，last[i]数组记录到当前i元素最短路径的元素的索引，与A*路径搜索代码极其类似，强烈建议查看！

状态：dp[i]为以nums[i]结尾的序列最长长度(该序列中所有元素能相互整除)
状态转移方程：dp[i] = dp[j] + 1;
状态初始化：dp定义的时候全部设置为0
输出：dp[i]中最大元素，然后根据最大元素回溯路径

376 摆动序列
状态中dp[i]必须是以元素i结尾的，才能找到dp[i]与dp[i-1]的关系，如果是前i个的话，就需要遍历所有的元素

状态定义：dp[i]，以diff[i](diff为相邻差数组)结尾的摆动子序列最长长度(不是前i个元素中，摆动子序列最长长度，这种需要遍历所有状态)
状态转移方程：若 diff[i] × diff[i-1] < 0， 则有 dp[i] = dp[i-1] + 1，表示最长摆动序列的长度加 1。否则dp[i] = dp[i-1]（因为nums[i]和nums[i-1]相同，所以最后一个元素可以用nums[i]替换nums[i-1]，序列长度不变）
状态初始化：dp[i]=2;
输出：dp[n]

377 组合总数-iv
与322 零钱兑换类似
当前状态与之前所有状态有关，这些状态通过nums[i]计算出来，有两层循环
自顶而上进行dfs搜索是可以的，但是题目没要求具体的数字，也可以自底而下进行求
难点在于理解dp[0]=1,必须能凑出来整数，否则有些数是凑不出来的

状态：dp[i]是以nums元素组成正整数 i 的的组合数目（不是以i去找nums，i是变化的，nums不变）
状态转移方程：dp[i]+=dp[i-nums[j]],dp[4]=dp[4-3]+dp[2]+dp[1]，三种之和（通过搜索树可以看出来）
状态初始化：dp[0]=1
输出：dp[target]

413 等差数列划分
相邻元素，索引之差为1。
以某个元素结尾的等差序列数目是a，下一个元素的数目是b，a和b是没有交集的。所有以元素结尾的数目相加，就是整个数组的数目了

状态定义：dp[i]对应的是以A[i]这个元素为结尾的子串中包含的等差数组的数目
状态转移方程：dp[i]=dp[i-1]+1
状态初始化：dp[i]=0
输出：所有dp元素之和

双一维状态定义
152 乘积最大子序列
要考虑存在负数的元素，则最大和最小值会交换，需要两个一维dp来分别记录最大最小值，由于只与前一个状态相关，可以进行空间压缩

状态：dp1[i]是以s[i]结尾的序列中最大连续子序列乘积，dp2[i]是以s[i]结尾的序列中最小连续子序列乘积
状态转移方程：dp1[i] = max(dp1[i-1]*nums[i], nums[i])与dp2[i] = min(dp2[i-1]*nums[i], nums[i]),负数乘以负数就变成了最大的正数，当前状态只与前一个状态有关
状态初始化：dp1[0]=nums[0], dp2[0]=nums[0]
输出：dp[n]中最大的值

213 打家劫舍ii
是198题的升级版本，家由原来的链状变成了环装，偷第一家不能偷最后一家，可以把数组拆分成两个链状，单独求，最后求较大的那个方案。代码中使用了一个i，比较tricky！

状态：dp1[i]为前i个房屋中偷第一家能偷盗金额最大值(含第i户)，dp2[i]为前i个房屋中不偷第一家能偷盗金额最大值(含第i户)
状态转移方程：dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i - 2])与dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i - 1]);
状态初始化：dp[0]=nums[0], dp[1]=max(nums[0], nums[1]);
输出：max(dp1[n], dp2[n])

309 最佳买卖股票时机含冰冻期
股票系列问题之一，需要对状态分为两个部分。当前状态与之前两个状态有关

状态定义：dp[i][0]和dp[i][1]分别代表第i天持有股票和不持有股票的最大收益
状态转移方程：hold[i] = max(hold[i - 1], unhold[i - 2] - prices[i]);与unhold[i] = max(hold[i - 1] + prices[i], unhold[i - 1]);
状态初始化：hold[0] = -prices[0]; hold[1] = max(-prices[0], -prices[1]);与        unhold[0] = 0; unhold[1] = max(prices[1] - prices[0], 0);
输出：hold和unhold中较大的值

二维状态定义——普通型
62 不同路径
根据题目要问的答案，直接定义出状态

状态：dp[i][j]为起始点到(i,j)的路径数目
状态转移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]
状态初始化：第一行和第一列都为1
输出：dp[m-1][n-1]，终点坐标

63 不同路径ii
考虑障碍物时，要对障碍物进行处理

状态：dp[i][j]为起始点到(i,j)的路径数目
状态转移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]，此时要判断(i,j)是否是障碍物，如果是的话，则不可到达，手动置为0
状态初始化：第一行和第一列都为1，如果有障碍物，则后面的数都为0
输出：dp[m-1][n-1]，终点坐标

64 最小路径和
和62题很类似，在地图中只能朝下或者右走

状态：dp[i][j]为起始点到(i,j)的路径最小和
状态转移方程：dp[i][j]=dp[i - 1][j] + dp[i][j - 1]，此时要判断(i,j)是否是障碍物，如果是的话，则不可到达，手动置为0
状态初始化：第一行和第一列累加，只有一条路径
输出：dp[m-1][n-1]，终点坐标

72 编辑距离
dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
这个解答非常详细的介绍了，https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/

状态定义：dp[i][j]是word1从0到i位置的字符串转换到word2的从0到j位置所需的最小步数
状态转移方程：dp[i][j] = dp[i-1][j-1]或dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1,不同的公式与word1[i] 与 word2[j]是否相同
状态初始化：dp[0][j]=j,dp[i][0]=i，前者是插入操作，后者是删除操作
输出：dp[m][n]

91 解码方法
和爬楼梯类似，对于连续的两个数可以分开处理，或者一起处理。要分类讨论(分类讨论其实就是用if进行逻辑控制)

状态定义：dp[i]为从首字符到s[i]的子串的解码方法数目
状态转移方程：状态转移方程：dp[i]=dp[i-1],if单独解码；dp[i]=dp[i-1] + dp[i-2] if联合解码。不是等式而是分类讨论或者归纳法
状态初始化：dp[0]=0，没有用到，dp[1]=1,只有一种方法
输出：dp[n]

120 三角形最小路径和
有两种思路，自顶而下和自底而上.注意不是贪心的思想，如果是贪心的思想求出来的结果是错的,因为贪心第一次求出来的结果不是最优的，没有考虑所有情况
自顶而下

状态定义：dp[i][j]表示从顶点到当前节点的最小路径和
状态转移方程：dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j]
状态初始化：dp[0][0]=triangle[0][0]
输出：dp[n][j]中的最小值

自底而上

状态定义：dp[i][j]表示从底到当前节点(i,j)的最小路径和
状态转移方程：dp[i][j] = min(dp[i+1][j-1],dp[i+1][j])+triangle[i][j]
状态初始化：dp[n][j]=triangle[n][j]，初始化最后一行为其自身的路径
输出：dp[0][0]中的最小值

221 最大正方形
把面积转换成边长，在matrix上画图分析，可以发现，dp[i][j]与其周围的三个状态有关，可以通过画图分析出来

状态：dp[i][j]为以(i,j)为右下角的最大正方形的边长(不是面积)
状态转移关系：dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
状态初始化：第一行和第一列，元素是1，则dp为1。dp[i][j] = matrix[i][j] - '0'
输出：dp中最大的元素

304 二维区域和检测——矩阵不可变
前缀和的二维版本，其实关键在于画图出来帮助理解状态转移方程。当前状态与之前三个状态有关。

状态定义:dp[i][j]为矩阵matrix中从(0,0)到(i,j)的矩形内所有元素之和
状态转移方程：sumRegion(row1, col1, row2, col2) = dp[row2][col2] - dp[row2][col1 - 1] - dp[row1 - 1][col2] + dp[row1 - 1][col1 - 1]
状态初始化：dp的第一行和列都为0，可以在定义dp的时候，整个dp都初始化为0
输出：dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1];

1143 最长公共子序列
在原有字符后同时添加一个字符，求dp[i][j]与dp[i-1][j-1]之间的关系，如果两个字符相同，则dp[i][j] = dp[i-1][j-1] + 1;，
如果不同，那至少要丢弃一个字符(因为要保持原字符串的相对序列，所以会由不同位置的相同字符来补上)，dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
当前状态dp[i][j]与0···j的所有状态，dp[i][0···j]都有关！

状态定义：dp[i][j]表示字符串s1从0到i与字符串s2从0到j之间的最长公共子序列的长度
状态转移方程： dp[i][j] = dp[i-1][j-1] + 1;与dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
状态初始化：dp[i][j]=0
输出：dp[n1][n2]

二维状态定义——区间型
5 最长回文串
状态的定义是定义一个子串的区间，很难直接发现。当前状态与之前所有状态有关，外层循环是长度，内层循环是起止位置，所有相同长度的子串遍历完后再遍历更长长度的子串

状态：dp[i][j]表示字符串从s[i]到s[j]是否为回文串，区间定义
状态转移方程：若s[i]==s[j]&&dp[i+1][j-1]==1，则dp[i][j]=1
初始化：二维表中对角线都为1(单个字符是回文串)，相邻相同的字符也需要考虑为回文串
输出：dp[start][max],通过这两个变量记录最长回文串的起止位置

375 猜数字大小
相对于easy的猜数字，medium的是不能用二分查找的，因为找到的是针对某个值，计算的金额是针对某个值的，题目要求是确保赢这个游戏，意味着需要足够金额保证，无论怎么猜(最坏的情况)都会赢
需要动态规划遍历所有的结果才知道最坏的情况猜需要的金额
先求长度为1的dp，然后长度为2....最后求长度为n
当前状态与之前的所有状态有关，有三层循环，比较复杂！！！
可以参考，https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/cai-shu-zi-da-xiao-ii-by-leetcode/

状态定义：dp[i][j]，在i到j区间中猜对数字需要的金额
状态转移方程：dp(i,j) = min​(pivot+max(dp(i,pivot−1),dp(pivot+1,n))),piovt遍历所有的i到j元素
状态初始化：dp[i][i] = 0;
输出：dp[1][n]

416 分割等和子集
0-1背包问题。
去凑j，有个选择是要不要用到nums[i]。不用，则dp[i][j] = dp[i-1][j];可能用，则dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
j - nums[i]，是指要用i-1个元素去凑 j 的剩下部分

状态：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
状态转移方程：dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
状态初始化：关于dp[0][j]和dp[i][0]的初始化为0
输出：dp[n][sum/2]

非leetcode题库1 0-1背包问题
0-1背包，每个物品最多只能放一次
有一个背包，他的容量为C(Capacity)。现在有n中不同的物品，编号为0…n-1，其中每一件物品的重量为w(i)，价值为v(i)。问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大。
对于dp(i,c)，有两种情况，将第i个物品加入和直接忽略第i个物品

状态定义：dp(i,j)将前 i 个物品放进容量为 j 的背包，使得价值最大。
状态转移方程： dp[i][j] = max( dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
状态初始化：初始化第一列，如果背包能够放下w[0]，则dp[0][j]=v[0]，其它部分在定义dp的时候初始化为0
输出：dp[n-1][C]

TODO：分析初始化dp长度是n还是n+1
dp的长度设计是n还是n+1，与状态转移方程有关，如果出现了i-2就得要n+1了

TODO：初始化的赋值，看看是否有规律