代码随想录算法训练营|动态规划三十八天~四十三天

动态规划五部曲：

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];
    }
}