代码随想录---动态规划篇

代码随想录—动态规划篇总结

动态规划的思路：

1.确定dp数组（dp table）以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组

一、509. 斐波那契数

int fib(int n) {
        if (n <= 1) return n;
        //1.dp[i]:F(i)
        vector<int> dp(n + 1, 0);
        //2.状态转移方程：dp[i] = dp[i - 1] + dp[i - 2];
        //3.初始化： dp[0] = F(0) = 0, dp[1] = F(1) = 1;
        dp[0] = 0, dp[1] = 1;
        //4.遍历顺序
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

二、70. 爬楼梯

int climbStairs(int n) {
        if (n <= 1) return n;
        //1.dp[i]:爬i阶楼梯不同的方法数
        vector<int> dp(n + 1, 0);
        //2.状态转移方程：dp[i] = dp[i - 1] + dp[i - 2];
        //3.初始化:
        dp[0] = 1, dp[1] = 1;
        //4.遍历顺序
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

三、746. 使用最小花费爬楼梯

int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        //1.dp[i]:爬上第i阶台阶的最低花费
        vector<int> dp(n + 1, 0);
        //2.状态转移方程：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        //3.初始化:
        dp[0] = dp[1] = 0;
        //4.遍历顺序
        for (int i = 2; i <= n; i++)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

四、62. 不同路径

int uniquePaths(int m, int n) {
        //1.dp[i][j]:到达第i行第j列的网格的路径数
        vector<vector<int>> dp(m, vector<int>(n, 0));
        //2.状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //3.初始化:机器人一直向下或者向右，只有一条路径
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        //4.遍历顺序
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

五、63. 不同路径 II

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //1.dp[i][j]:到达第i行第j列的网格的路径数
        int n = obstacleGrid[0].size();
        int m = obstacleGrid.size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        //2.状态转移方程：if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        //3.初始化:机器人一直向下或者向右，只有一条路径,并且障碍物无法到达，故初始化为0
        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] != 1; j++) dp[0][j] = 1;
        //4.遍历顺序
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

六、343. 整数拆分

int integerBreak(int n) {
        if (n <= 1) return n;

        //1.dp[i]:正整数i可以拆分成整数的乘积最大
        vector<int> dp(n + 1, 0);
        //(i - j) * j 代表可以拆成两个整数
        //max(dp[i - j] * j：代表可以拆成两个以上的整数
        //2.状态转移方程：dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
        //3.初始化:0的最大乘积是0， 1的最大乘积是1
        dp[0] = 0, dp[1] = 1;
        //4.遍历顺序 j只需要到i / 2,因为dp[j] * d[i - j] == dp[i - j] * dp[j];
        for (int i = 2; i <= n; i++)
        {
            for (int j = 0; j <= i / 2; j++)
            {
                dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[n];
    }

七、不同的二叉搜索树

int numTrees(int n) {
        //1.dp[i]:由i个节点组成的二叉搜索树的数量
        vector<int> dp(n + 1, 0);
        //2.状态转移方程：dp[i] += dp[j] * dp[i - j - 1];
        //3.初始化:对于0个节点，有1个二叉搜索树
        dp[0] = 1;
        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }

八、01背包理论基础

1.二维数组表示

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> m >> n;
    vector<int> weight(m, 0), value(m, 0);
    for (int i = 0; i < m; i++) cin >> weight[i];
    for (int i = 0; i < m; i++) cin >> value[i];
    //1.dp[i][j]:前i个物品所占的空间为j时的最大价值
    vector<vector<int>> dp(m, vector<int>(n + 1, 0));
    //2.状态转移方程:dp[i][j] = dp[i - 1][j];
    //if (j >= nums[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);

    //3.初始化：初始化dp[0][0..n]
    for (int j = 0; j <= n; j++) if (j >= weight[0]) dp[0][j] = value[0];

    //4.遍历顺序
    for (int i = 1; i < m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= weight[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

    cout << dp[m - 1][n] << endl;
    return 0;
}

2.一维数组表示

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> m >> n;
    vector<int> weight(m, 0), value(m, 0);
    for (int i = 0; i < m; i++) cin >> weight[i];
    for (int i = 0; i < m; i++) cin >> value[i];
    //1.dp[j]:所占的空间为j时的最大价值
    vector<int> dp(n + 1, 0);
    //2.状态转移方程:if (j >= nums[i]) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    //3.初始化：无需初始化

    //4.遍历顺序：i从0->m - 1, j为了防止覆盖，需要从n -> 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = n; j >= weight[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << dp[n] << endl;
    return 0;
}

九、416. 分割等和子集

bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (sum % 2) return false;
        int target = sum / 2;
        
        //1.dp[j]：要求的值为j时可以组成的最大值为dp[j];
        vector<int> dp(target + 1, 0);
        //2.状态转移方程: if (j >= nums[i]) dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        //3.初始化：无需初始化
        //4.遍历顺序：i从0->nums.size() - 1, j为了防止覆盖，需要从target -> 0;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = target; j >= nums[i]; j--)
            {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;
    }

十、1049. 最后一块石头的重量 II

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum = 0;
        for (int i = 0; i < n; i++) sum += stones[i];
        int target = sum / 2;

        //1.dp[i][j]:前i个石头且重量要求为j时可以装的最大重量
        vector<vector<int>> dp(n, vector<int>(target + 1, 0));
        //2.状态转移方程：dp[i][j] = dp[i - 1][j];
        //else dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i]] + stones[i]);
        //3.初始化:
        for (int j = 0; j <= target; j++) if (j >= stones[0]) dp[0][j] = stones[0];
        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= target; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= stones[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i]] + stones[i]);
            }
        }

        return (sum - dp[n - 1][target] - dp[n - 1][target]);
    }
};

十一、494. 目标和

//组合问题
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; i++) sum += nums[i];
        if (abs(target) > sum) return 0;
        if ((target + sum) % 2) return 0;
        int bagSize = (target + sum) / 2;
        
        //1.dp[j]:重量为j的背包可以装下的组合数目
        vector<vector<int>> dp(n, vector<int>(bagSize + 1, 0));
        //2.状态转移方程：dp[i][j] = d[i - 1][j]; //不考虑第i件物品的方法
        //if (j >= nums[i]) dp[i][j] += dp[i - 1][j - nums[i]]; //考虑第i件物品的方法

        //3.初始化：只考虑第0个物品，只有当物品可以完全装满背包时算一种方法
        for (int j = 0; j <= bagSize; j++) if (j == nums[0]) dp[0][j] = 1;
        //当背包容量为0时，不装物品也算一种方法,但是如果出现0，那么方法数量就是2 ^ (0的个数）
        int zeroNum = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 0) zeroNum++;
            dp[i][0] = pow(2.0, zeroNum);
        }

        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j <= bagSize; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i]) dp[i][j] += dp[i - 1][j - nums[i]];
            }
        }

        return dp[n - 1][bagSize];
    }

十二、474. 一和零

int findMaxForm(vector<string>& strs, int m, int n) {
        //1.dp[i][j]:i个0j个1可以组成的最大子集个数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        //2.状态转移方程：dp[i][j] = max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1);
        //3.初始化:所有的值默认为0
        for (int i = 0; i < strs.size(); i++)
        {
            int zeroCount = 0, oneCount = 0;
            for (char c : strs[i])
            {
                if (c == '0') zeroCount++;
                else oneCount++;
            }
            //4.遍历顺序：相比于01背包，我们此处的jk都是背包容量那个维度的值，相当于滚动数组那块的逆序遍历
            for (int j = m; j >= zeroCount; j--)
            {
                for (int k = n; k >= oneCount; k--)
                {
                    dp[j][k] = max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
                }
            }
        }
        return dp[m][n];
    }

十三、完全背包理论基础

1.二维数组表示

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, v;
    cin >> n >> v;
    vector<int> weight(n, 0), value(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i] >> value[i];
    
    //1.dp[i][j]:前i个物体（可以无限次使用）装入容量为j的背包中表示的最大价值
    vector<vector<int>> dp(n, vector<int>(v + 1, 0));
    //2.状态转移公式:dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
    //3.初始化：初始化第0件物品
    for (int j = weight[0]; j <= v; j++) dp[0][j] = value[0] * (j / weight[0]);
    //4.遍历顺序
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= v; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= weight[i]) dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
        }
    }

    cout << dp[n - 1][v] << endl;
    return 0;
}

2.一维数组表示

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, v;
    cin >> n >> v;
    vector<int> weight(n, 0), value(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i] >> value[i];
    
    //1.dp[j]:（可以无限次使用）物品装入容量为j的背包中表示的最大价值
    vector<int> dp(v + 1, 0);
    //2.状态转移公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    //3.初始化：无需初始化
    //4.遍历顺序
    for (int i = 0; i < n; i++)
    {
        for (int j = weight[i]; j <= v; j++)
        {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << dp[v] << endl;
    return 0;
}

十四、518. 零钱兑换 II — 组合问题

//完全背包问题,组合数
    int change(int amount, vector<int>& coins) {
        //1.dp[j]:组成总金额为j的组合数
        vector<int> dp(amount + 1, 0);
        //2.状态转移方程：dp[j] += dp[j - coins[i]];(看到组合数就要想到这个转移方程)
        //3.初始化:组合问题必须需要初始化，否则结果全为0(肥肠重要，每次我都记不住)
        dp[0] = 1;
        //4.遍历顺序
        for (int i = 0; i < coins.size(); i++)
        {
            for (int j = coins[i]; j <= amount; j++)
            {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }

十五、377. 组合总和 Ⅳ — 排列问题

//完全背包问题，排列数
    int combinationSum4(vector<int>& nums, int target) {
        //1.dp[i]:组成target的排列个数
        vector<uint64_t> dp(target + 1, 0);
        //2.状态转移方程：dp[i] += dp[i - coins[j]];(看到组合数排列数就要想到这个转移方程)
        //3.初始化:排列组合问题必须需要初始化，否则结果全为0(肥肠重要，每次我都记不住)
        dp[0] = 1;
        //4.遍历顺序:相比于组合问题，排列问题就需要先便利目标数，在遍历nums数组，这样才能有排列的效果
        for (int i = 0; i <= target; i++)
        {
            for (int j = 0; j < nums.size(); j++)
            {
                if (i >= nums[j]) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }

十六、57. 爬楼梯（第八期模拟笔试） — 排列问题

#include <iostream>
#include <vector>

 using namespace std;

//完全背包问题，排列问题
 int main()
 {
    int n, m;
    cin >> n >> m;
    //1.dp[i]:爬至第i阶楼梯有dp[i]种不同的方法
    vector<int> dp(n + 1, 0);
    //2.状态转移方程:dp[i] += dp[i - j];
    //3.初始化:
    dp[0] = 1;
    //4.遍历顺序
    for (int i = 0; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i >= j) dp[i] += dp[i - j];
        }
    }

    cout << dp[n];
    return 0;
 }

十七、322. 零钱兑换

//完全背包问题，组合数
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        //1.dp[j]:凑成总金额j所需的最少的硬币个数.
        vector<uint64_t> dp(amount + 1, INT_MAX);
        //2.状态转移方程:dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        //3.初始化：
        dp[0] = 0;
        //4.遍历顺序
        for (int i = 0; i < n; i++)
        {
            for (int j = coins[i]; j <= amount; j++)
            {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        if (dp[amount] >= INT_MAX) return -1;
        return dp[amount];
    }

十八、279. 完全平方数

//完全背包问题，组合问题
    int numSquares(int n) {
        //1.dp[j]：和为 j 的完全平方数的最少数量.
        vector<uint64_t> dp(n + 1, INT_MAX);
        //2.状态转移方程：dp[j] = min(dp[j], dp[j - i * i] + 1);
        //3.初始化：
        dp[0] = 0;
        //4.遍历顺序：
        for (int i = 1; i * i <= n; i++)
        {
            for (int j = i * i; j <= n; j++)
            {
                dp[j] = min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];
    }

十九、139. 单词拆分

//完全背包问题，排列问题
    bool wordBreak(string s, vector<string>& wordDict) {
        //匹配单词的哈希表
        unordered_set<string> uset(wordDict.begin(), wordDict.end());

        int n = s.size();
        //1.dp[i]:前i个字符是否可以用wordDict的字符串列表作为字典
        vector<bool> dp(n + 1, false);
        //2.状态转移方程：if (word == 可以被匹配 dp[j] = true) dp[i] = true;
        //3.初始化:没有实际意义，但是为了保证结果正确
        dp[0] = true;
        //4.遍历顺序:先背包后物品，这块的物品是需要我们自己匹配的，所以我们需要从0开始遍历物品
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                string word = s.substr(j, i - j);
                if (uset.find(word) != uset.end() && dp[j] == true) dp[i] = true; 
            }
        }

        //for (int i = 0; i <= n; i++) cout << dp[i] << " ";

        return dp[n];
    }

二十、56. 携带矿石资源（第八期模拟笔试）

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int c, n;
    cin >> c >> n;
    vector<int> weight(n, 0), value(n, 0), nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];

    //1.dp[i][j]:前i个物品装入容量为j的背包可以存储的最大价值
    vector<vector<int>> dp(n, vector<int>(c + 1, 0));
    //2.状态转移方程:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);

    //3.初始化
    for (int j = 0; j <= c; j++)
    {
        if (j / weight[0] >= nums[0]) dp[0][j] = value[0] * nums[0];
        else dp[0][j] = value[0] * (j / weight[0]);
    }

    //4.遍历顺序
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j <= c; j++)
        {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k <= nums[i]; k++)
            {
                if (j >= k * weight[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
            }
        }
    }

    cout << dp[n - 1][c];

    return 0;
}

二十一、198. 打家劫舍

int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        

        //1.dp[i]:盗取第i间房屋的最高金额
        vector<int> dp(n, 0);
        
        //2.状态转移方程：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        //3.初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        //4.遍历顺序
        for (int i = 2; i < n; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }

二十二、213. 打家劫舍 II

int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];

        //如果连成一个圈的话，那么就需要分成三种情况，1.考虑第一个不考虑最后一个；
        //2.考虑最后一个不考虑第一个
        //3.第一个和最后一个都不考虑
        //最后取得最大值，但是第一种情况和第二种情况中会包含第三种情况，所以只需要遍历1，2就可以了
        return max(RobRange(nums, 0, nums.size() - 2), RobRange(nums, 1, nums.size() - 1));
    }

    int RobRange(vector<int> nums, int begin, int end)
    {
        int n = nums.size();
        if (begin == end) return nums[begin];
        
        //1.dp[i]:盗取第i间房屋的最高金额
        vector<int> dp(n, 0);
        
        //2.状态转移方程：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        //3.初始化
        dp[begin] = nums[begin];
        dp[begin + 1] = max(nums[begin], nums[begin + 1]);

        //4.第一种情况
        for (int i = begin + 2; i <= end; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[end];
    }

二十三、337. 打家劫舍 III

//只能使用后序遍历
    //0表示不偷该节点，1表示偷该节点
    vector<int> robTree(TreeNode* cur)
    {
        if (cur == nullptr) return {0, 0};
        
        vector<int> left = robTree(cur -> left);
        vector<int> right = robTree(cur -> right);

        //偷该节点
        int val1 = cur -> val + left[0] + right[0];
        //不偷该节点,考虑是否偷子节点
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);

        return {val2, val1};
    }

    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }

二十四、121. 买卖股票的最佳时机

//动态规划
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        //1.dp[i][0]:第i天没有持有股票时身上的钱
        //dp[i][1]:第i天持有股票时身上的钱
        vector<vector<int>> dp(n, vector<int>(2, 0));

        //2.状态转移方程:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        //dp[i][1] = max(dp[i - 1][1], -prices[i]); //只能买一个，所以直接是-prices

        //3.初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        //4.遍历顺序：依次遍历
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], -prices[i]);
        }

        return dp[n - 1][0];
    }

二十五、122. 买卖股票的最佳时机 II

int maxProfit(vector<int>& prices) {
        int n = prices.size();

        //1.dp[i][0]:第i天没有持有股票时身上的钱
        //dp[i][1]:第i天持有股票时身上的钱
        vector<vector<int>> dp(n, vector<int>(2, 0));

        //2.状态转移方程:dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        //dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

        //3.初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        //4.遍历顺序：依次遍历
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[n - 1][0];
    }

二十六、123. 买卖股票的最佳时机 III

//相对于之前的买卖股票的两个状态，这次需要四种状态
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        //1.dp[i][0]:第i天第一次持有股票是身上的钱
        //dp[i][1]:第i天第一次卖出股票是身上的钱
        //dp[i][2]:第i天第二次持有股票是身上的钱
        //dp[i][3]:第i天第二次卖出股票是身上的钱
        vector<vector<int>> dp(n, vector<int>(4, 0));

        //2.状态转移方程:dp[i][0] = max(dp[i - 1][0], -prices[i]);
        //dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        //dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
        //dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);

        //3.初始化
        dp[0][0] = -prices[0]; dp[0][2] = -prices[0];
        dp[0][1] = 0; dp[0][3] = 0; 

        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }

        return max(dp[n - 1][1], dp[n - 1][3]);
    }

二十七、188. 买卖股票的最佳时机 IV

int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();

        //1.dp数组含义与之前的类似，但是dp[i][0]:没有经过任何操作获得的利润，剩下的依次类推
        vector<vector<int>> dp(n, vector<int>(2 * k + 1, 0));
        //2.状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])

        //3.状态初始化
        for (int j = 1; j <= 2 * k; j += 2) dp[0][j] = -prices[0];

        //4.遍历顺序：依次遍历即可
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j <= 2 * k; j += 2)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }

        int result = 0;
        for (int j = 0; j <= 2 * k; j += 2) result = max(result, dp[n - 1][j]);

        return result;
    }

二十八、309. 买卖股票的最佳时机含冷冻期

int maxProfit(vector<int>& prices) {
        int n = prices.size();

        //1.dp[i][0]:第i天持有股票时身上的钱
        //dp[i][1]:第i天身上未持有股票时身上的钱（同时已经过了冷冻期）
        //dp[i][2]:第i天当天出售身上的股票后身上的钱
        //dp[i][3]:第i天处于冷冻期
        vector<vector<int>> dp(n, vector<int>(4, 0));

        //2.状态转移方程
        //dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        //dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
        //dp[i][2] = dp[i - 1][0] + prices[i];
        //dp[i][3] = dp[i - 1][2];

        //3.初始化:dp[0][1,2,3] = 0
        dp[0][0] = -prices[0];

        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }

        return max(dp[n - 1][1], max(dp[n - 1][2], dp[n - 1][3]));
    }

二十九、714. 买卖股票的最佳时机含手续费

int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        
        //1.dp[i][0]:第i天身上有股票时的最大利润
        //dp[i][1]:第i天身上卖出股票时的最大利润
        vector<vector<int>> dp(n, vector<int>(2, 0));

        //2.状态转移方程：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
        //dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

        //3.初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }

        return dp[n - 1][1];
    }

三十、718. 最长重复子数组

int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int result = 0;

        //1.dp[i][j]:nums1的前i个字符与nums2的前j个字符的最长重复子数组大小
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程
        //if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j -1] + 1;

        //3.初始化

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                result = max(result, dp[i][j]);
            }
        }

        return result;
    }

三十一、1143. 最长公共子序列

int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        int result = 0;

        //1.dp[i][j]:nums1的前i个字符与nums2的前j个字符的最长重复子数组大小
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程 if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        // else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        //3.初始化 dp[0][0] = 0; 上面已经初始化过了

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n][m];
    }

三十二、718. 最长重复子数组

int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int result = 0;

        //1.dp[i][j]:nums1的前i个字符与nums2的前j个字符的最长重复子数组大小
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程
        //if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j -1] + 1;

        //3.初始化

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                result = max(result, dp[i][j]);
            }
        }

        return result;
    }

三十三、1143. 最长公共子序列

int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        int result = 0;

        //1.dp[i][j]:nums1的前i个字符与nums2的前j个字符的最长重复子数组大小
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程 if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        // else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        //3.初始化 dp[0][0] = 0; 上面已经初始化过了

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n][m];
    }

三十四、1035. 不相交的线

//理解题意的话，其实就是求最长公共子序列
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();

        //1.dp[i][j]:nums1的前i - 1个字符与nums2的前j - 1个字符的最长公共子序列的长度
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程:if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        //else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

        //3.初始化：dp[0][0] = 0;

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[n][m];
    }

三十五、53. 最大子数组和

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        

        //1.dp[i]:从0到i的数组中组成的连续子数组最大和
        vector<int> dp(n, 0);

        //2.状态转移方程：if (dp[i - 1] + nums[i] >= 0) dp[i] = dp[i - 1] + nums[i];

        //3.初始化 
        dp[0] = nums[0];
        int result = nums[0];

        //4.遍历顺序
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            result = max(result, dp[i]);
        }

        return result;
    }

三十六、392. 判断子序列

bool isSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();

        //1.dp[i][j]:s的前i - 1个字符中t的前j - 1个字符的子序列的数量
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        //2.状态转移方程：if (s[i - 1] == t[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;
        //else dp[i][j] = dp[i][j - 1];

        //3.初始化：dp[0][0] = dp[0][1] = dp[1][0] = 0;

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            } 
        }

        return dp[n][m] == n;
    }

三十七、115. 不同的子序列

int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();

        //1.dp[i][j]:t的前j - 1的子序列在s的前i - 1的子序列中出现的个数
        vector<vector<uint64_t>> dp(n + 1, vector<uint64_t>(m + 1, 0));

        //2.状态转移方程：if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        //else dp[i][j] = dp[i - 1][j];

        //3.初始化
        for (int i = 1; i <= n; i++) dp[i][0] = 1;
        for (int j = 1; j <= m; j++) dp[0][j] = 0;
        dp[0][0] = 1;
        
        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[n][m];
    }

三十八、583. 两个字符串的删除操作

int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();

        //1.dp[i][j]:word1的前i个字符与word2的前j个字符相同的话所需的步数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));

        //2.状态转移方程：if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
        //else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;

        //3.初始化
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }

        return dp[n][m];
    }

三十九、72. 编辑距离

int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();

        //1.dp[i][j]:word1的前i个字符转换成word2的前j个字符所需要的最少操作数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));

        //2.状态转移方程:if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
        //else dp[i][j] = min(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1])) + 1;  删除和插入可以看成一种操作
        //替换相当于将不相等的字符换成相同的那个，也就是 dp[i - 1][j - 1] + 1;

        //3.初始化
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 1; j <= m; j++) dp[0][j] = j;

        //4.遍历顺序
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }

        return dp[n][m];
    }

四十、647. 回文子串

int countSubstrings(string s) {
        int n = s.size();
        int result = 0;
        
        //1.dp[i][j]:字符串s的i-j的字符串是不是回文串
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        //2.状态转移方程 if (s[i] == s[j]) {if (j - i <= 1) dp[i][j] = true; 
        //else if (dp[i + 1][j - 1]) dp[i][j] = true }

        //3.初始化

        //4.遍历顺序：根据状态转移方程可得，dp数组更新依赖于其左下角的值,并且i <= j
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    if (j - i <= 1) dp[i][j] = true;
                    else if (dp[i + 1][j - 1]) dp[i][j] = true;
                }

                if (dp[i][j]) result++;
            }
        }

        return result;
    }

四十一、516. 最长回文子序列

int longestPalindromeSubseq(string s) {
        int n = s.size();
        
        //1.dp[i][j]:s的[i,j]范围内的最长的回文子序列的长度
        vector<vector<int>> dp(n, vector<int>(n, 0));

        //2.状态转移方程:if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
        //else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

        //3.初始化 
        for (int i = 0; i < n; i++) dp[i][i] = 1;

        //4.遍历顺序
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        return dp[0][n - 1];
    }

总结

上述是对我学习的代码随想录的动态规划篇的总结，里面有着我对这些代码的想法以及卡哥带给我的思路。