动态规划五部曲：
1、确定dp数组以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组
三十八天
斐波那契数
509. 斐波那契数 - 力扣（LeetCode）
public class Solution {
public int MonotoneIncreasingDigits(int n) {
string s = n.ToString();
int size = s.Length;
for(int i=s.Length-1;i>0;i--){
if(s[i-1] > s[i]){
size=i;
s = s.Substring(0,i-1)+(char)(s[i-1]-1)+s.Substring(i);
}
}
for(int i=size;i<s.Length;i++){
s = s.Substring(0,i)+'9'+s.Substring(i+1);
}
return int.Parse(s);
}
}爬楼梯
70. 爬楼梯 - 力扣（LeetCode）
public class Solution {
public int ClimbStairs(int n) {
if(n==1){return n;}
int[] result = new int[n+1];
result[1] = 1;
result[2] = 2;
for(int i=3;i<=n;i++){
result[i] = result[i-1]+result[i-2];
}
return result[n];
}
}使用最少花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
if(cost.Length == 1){return 0;}
int[] result = new int[cost.Length+1];
result[0] = 0;
result[1] = 0;
for(int i=2;i<=cost.Length;i++){
result[i] = Math.Min(result[i-1]+cost[i-1],result[i-2]+cost[i-2]);
}
return result[cost.Length];
}
}三十九天
不同路径
62. 不同路径 - 力扣（LeetCode）
按照五部曲，dp数组含义是从起点到[i,j]的路径总共有result[i,j]条路径；递归就是在点[0,0]到[1,1]有两条路，即[0,1]和[1,0]，所以result[i,j]=result[i-1,j]+result[i,j-1]；初始化就把纵横赋值为1，因为只有一个方法走，
public class Solution {
public int UniquePaths(int m, int n) {
int[,] result = new int[n,m];
for(int i=0;i<n;i++){result[i,0] = 1;}
for(int j=0;j<m;j++){result[0,j] = 1;}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
result[i,j] = result[i-1,j] + result[i,j-1];
}
}
return result[n-1,m-1];
}
}不同路径||
63. 不同路径 II - 力扣（LeetCode）
和上一题比就多了个障碍，只要把障碍的位置记录就行了。
public class Solution {
public int UniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.Length;
int m = obstacleGrid[0].Length;
int[,] result = new int[n,m];
if(obstacleGrid[n-1][m-1] == 1 || obstacleGrid[0][0] == 1){return 0;}
for(int i=0;i<n && obstacleGrid[i][0] == 0;i++){
result[i,0] = 1;
}
for(int i=0;i<m && obstacleGrid[0][i] == 0;i++){
result[0,i] = 1;
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(obstacleGrid[i][j] != 1){
result[i,j] = result[i-1,j]+result[i,j-1];
}
}
}
return result[n-1,m-1];
}
}四十天
整数拆分
343. 整数拆分 - 力扣（LeetCode）
要点：这题递推比较难，有两个拆分方向，一个是j*（i-j），一个是j*result[i-j]。例如输入5，拆分1，4，然后4可以继续拆分成1，3，然后就取1*4和1*1*3的最大值，再赋值到result[i]
public class Solution {
public int IntegerBreak(int n) {
int[] result = new int[n+1];
result[2] = 1;
for(int i=3;i<=n;i++){
for(int j=1;j<i-1;j++){
result[i] = Math.Max(result[i],Math.Max(j*(i-j),j*result[i-j]));
}
}
return result[n];
}
}不同的二叉搜索树
96. 不同的二叉搜索树 - 力扣（LeetCode）
要点：首先就是二叉树的左边比头结点小，右边比头结点大，其次，根据例题输入n=3，图，以及二叉树的特性，能推断出result[3] = result[2]*result[0] + result[1]*result[1] + result[0]*result[2]，就是左子树元素节点数量*右子树元素节点数量。
关于result[0]=1：
从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。
从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
public class Solution {
public int NumTrees(int n) {
int[] result = new int[n+1];
result[0] = 1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
result[i] += result[j-1]*result[i-j];
}
}
return result[n];
}
}四十一天
背包问题
二维dp数组01背包：（详细看代码随想录 (programmercarl.com)）
1、dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2、递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
不放物品i：dp[i - 1][j]（由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同）；
放物品：dp[i - 1][j - weight[i]] + value[i]（由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值）。
3、初始化
从dp[0][0]开始，纵向初始化为0，横向i>0，都初始化为物品0能放进背包时的价值，放不进也初始化为0；其他的也都可以初始化为0。
4、遍历顺序：
先遍历物品或者背包都可以。
先遍历物品
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}一维数组（滚动数组，就是每次循环都覆盖在原来的数组中，二维数组是i*j的数组，一维数组只需要j）
1、dp[j]表示容量为j的背包，所背的物品价值可以最大为dp[j]。
2、递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3、初始化：全部初始为0.
4、遍历顺序
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}分割等和字集
416. 分割等和子集 - 力扣（LeetCode）
要点：这题是前面背包问题的应用，然后一维数组的递推公式在这里的平替是背包体积是target，重量和价值是nums。不过我还没完全懂，先挂在这后面慢慢想。
public class Solution {
public bool CanPartition(int[] nums) {
bool[] dp = new bool[10000];
int sum = nums.Sum();
if(sum % 2 == 1){return false;}
int target = sum / 2;
dp[0] =true;
for(int i=0;i<nums.Length;i++){
for(int j=target;j>=nums[i];j--){
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
}四十二天
最后一块石头的重量||
1049. 最后一块石头的重量 II - 力扣（LeetCode）
和分割等和子集同样的思路
public class Solution {
public int LastStoneWeightII(int[] stones) {
int sum = stones.Sum();
int target = sum/2;
int[] dp = new int[target+1];
for(int i=0;i<stones.Length;i++){
for(int j=target;j>=stones[i];j--){
dp[j] = Math.Max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum - 2*dp[target];
}
}目标和
494. 目标和 - 力扣（LeetCode）
public class Solution {
public int FindTargetSumWays(int[] nums, int target) {
int sum = nums.Sum();
if(Math.Abs(target) > sum){return 0;}
if((target+sum)%2 == 1){return 0;}
int bagLength = (target+sum) / 2;
int[] dp = new int[bagLength+1];
dp[0] = 1;
for(int i=0;i<nums.Length;i++){
for(int j=bagLength;j>=nums[i];j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[bagLength];
}
}一和零
474. 一和零 - 力扣（LeetCode）
public class Solution {
public int FindMaxForm(string[] strs, int m, int n) {
int[,] dp= new int[m+1,n+1];
foreach(string s in strs){
int zeroNum = 0;
int oneNum = 0;
foreach(char a in s){
if(a == '0')zeroNum++;
else oneNum++;
}
for(int i=m;i>=zeroNum;i--){
for(int j=n;j>=oneNum;j--){
dp[i,j] = Math.Max(dp[i,j],dp[i-zeroNum,j-oneNum]+1);
}
}
}
return dp[m,n];
}
}目前，我对所有的01背包问题都不懂！
四十三天
完全背包：所有物品都能无限放入背包
零钱兑换||
518. 零钱兑换 II - 力扣（LeetCode）
看起来和那个目标和的题差不多，对物品的使用次数没限制。不过还是不太懂。
public class Solution {
public int Change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i=0;i<coins.Length;i++){
for(int j = coins[i];j<=amount;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}组合总和IV
377. 组合总和 Ⅳ - 力扣（LeetCode）
public class Solution {
public int CombinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i <= target; i++) {
for (int j = 0; j < nums.Length; j++) {
if (i - nums[j] >= 0 && dp[i] < int.MaxValue - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
