代码随想录动态规划 | 小结一
动态规划理论基础
动规五部曲：
1.确定dp数组及其下标含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
斐波那契数列
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
爬楼梯
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
初始化dp数组的时候，dp[0]的初始化其实是没有含义的。
正确的思路是：dp[1] = 1,dp[2]=2，从3开始遍历。
使用最小花费爬楼梯
推导现在的状态怎么出现的：（爬上当前楼梯不需要花费，在前一阶已经花了）
状态转移方程：dp[i] = min(dp[[i-1]+costs[i] , dp[i-2] + costs[i-2])
不同路径
从出发点到终点有几种路径。
dp[i] [j] = 从左边+从上面来的路径 = dp[i-1] [j] + dp[i] [j-1]
需要注意数组初始化！最左、最上的边框都需要初始化为1，因为只有一条路径能都到达。
不同路径（添加障碍版）
从出发点到终点有几种路径。
（ ( i , j )没有障碍时）dp[i] [j] = 从左边+从上面来的路径 = dp[i-1] [j] + dp[i] [j-1]
需要注意数组初始化！最左、最上的边框（在障碍之前的）都需要初始化为1，因为只有一条路径能都到达，被障碍挡住的路径不可达。
整数拆分
将数字 i 拆成两种：j*(i-j) / j *dp[i-j]
类似于2 ： 1*(2-1) / 1 *dp[2-1]
以及需要选取乘积最大化：需要循环比较
因此递推公式：dp[j] = max( dp[j] , max(j(i-j) , j * dp[i-j]) )*
不同的二叉搜索树
给出n个不同的节点求能组成多少个不同的二叉搜索树
2为节点的时候有两个不同的二叉树：1为头结点，2为右子树 、2为头结点，1为左子树
*dp[i] += dp[i-j]dp[j-1] (1为头结点时，左子树有0个元素，右子树有2个元素 )
01背包理论基础
二维数组
1.确定dp数组及其下标含义
dp[i] [j]：表示从下标为[ 0 - i ]的物品里任意取，放进容量为j的背包，价值总和最大是多少
2.确定递推公式
dp[i] [j] = max(dp[i-1] [j] , dp[i-1] [j-weight[i]]+values[i])
3.数组初始化
按照题意来。非零下标，如果题意给的都是正整数则初始化为0；求最小值则初始化为最大值（Math.MaxInt）
4.确定遍历顺序
01背包二维dp数组在遍历顺序上，无论是外层物品、里层背包或外层背包、里层物品都是可以的。
5.举例推导。。
一维数组
和二维数组的区别：背包的状态是可以压缩的 =》压缩为一维数组
二维数组定义：dp[i] [j]：表示从下标为[ 0 - i ]的物品里任意取，放进容量为j的背包，价值总和最大是多少
1.确定dp数组及其下标含义
dp[j]：容量为 j 的背包，所背的物品价值最大为dp[j]
2.一维dp数组的递推公式
dp[j] = max(dp[j],dp[j - weight[i]] + values[i])
3.数组初始化
如果物品价值都是大于0的，dp数组初始化的时候初始化为0即可。
4.一维dp数组遍历顺序
外层为物品，内层为背包且倒序遍历。
5.举例推导dp数组。。
分割等和子集
将总和sum分为一半，即target = sum/2为背包的最大容量，元素的数值为物品
dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])
如果dp[target] == target ，说明集合中的子集总和正好可以凑成总和 j。
最后一块石头的重量
和上题类似、将石头尽可能分成重量相同的两份，然后sum - 2*dp[target] 就好啦
目标和
要求在数列之间加入+或-，使其和为target，有多少种组合。
本题我们通过求出target、sum、加法集合、减法集合的等式：left = (target + sum)/2
求组合数量 =》累加 ，因为累加需要数组初始化时不为0 且 dp[0]说明数组里的元素0前面无论是放加法还是减法都属于一种方法，因此dp[0] = 0
dp[j] += dp[j - nums[i]]
一维数组、物品外循环，背包内循环且倒序
一和零
数组里面有任意个由0和1组成的字符串
关键词：0和1的数量有限，因此我们应该使用01背包。把0和1 当作两个维度的背包，str当作物品
求出0和1的数量为多少
递推公式：dp[i] [j] = max(dp[i] [j] ,dp[i-zeroNum] [j-oneNum] +1 )
i 和 j 的范围为zeroNum - m ,oneNum - n ，且需要倒序遍历！（背包维度）
完全背包理论
完全背包和01背包区别在于：完全背包的物品数量是无限。
完全背包的物品可以添加多次，因此遍历背包容量要从小到大遍历。
排列数：背包在外循环遍历，物品在内循环遍历
组合数（去重）：物品在外循环遍历，背包在内循环正序遍历 – 保证了物品只被遍历一次
零钱兑换II
求一共有多少种凑成总金额的组合数，要求去重，因此物品（coins）在外循环，背包（amount）在内循环。
推导公式：dp[j] += dp[j - i]
i : 1 - coins.length / j : coin[i] - amont
组合总和IV
求排列数，因此背包（target）在外循环，物品（nums）在内循环
推导公式：dp[i] += dp[i- nums[j]]
爬楼梯
求总数，使用累加。
背包（n阶）在外循环，物品（m层跳跃）在内循环
推导公式：dp[i] += dp[i-j]
零钱兑换
求所需最少，且数量无限，完全背包。
数组初始化为最大值，以免数值被初始值覆盖。
背包（amount）在外循环，物品（coins）在内循环。
dp[i] = min(dp[i-coins[j]] +1 , dp[i])
完全平方数
将完全平方数看作物品！
dp[j] = min(dp[j] , dp[j - i*i] + 1)
要记得dp[j - weight[i]] + values[i]
写了五小时终于写完了总结XD。。。
