【数据结构与算法】LeetCode： 动态规划

Leetcode 动态规划

动态规划基础

杨辉三角 （Hot 100）

杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dp(numRows);
        for (int i = 0; i < numRows; ++i) {
            dp[i].resize(i + 1);
            dp[i][0] = dp[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        return dp;
    }
};

斐波那契数

斐波那契数

class Solution {
public:
    int fib(int n) {
        if(n <= 1) return n;
        vector<int> dp(n+1);  // [0,n]
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
            dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
};

空间优化：

class Solution {
public:
    int fib(int n) {
        if(n <= 1) return n;
        int dp0 = 0;
        int dp1 = 1;
        for(int i = 2; i <= n; i++){
            int sum = dp0 + dp1;
            dp0 = dp1;
            dp1 = sum;
        }

        return dp1;
    }
};

爬楼梯 （Hot 100）

爬楼梯
dp[i]： 爬到第i层楼梯，有dp[i]种方法

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        int dp0 = 1, dp1  = 2, dpi = 0;
        for (int i = 3; i <= n; ++i) {
            dpi = dp0  + dp1  ;
            dp0  = dp1  ; 
            dp1   = dpi ; 

        }
        return dpi ;
    }
};

使用最小花费爬楼梯

使用最小花费爬楼梯

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp0 = 0;
        int dp1 = 0;
        for (int i = 2; i <= cost.size(); i++) {
            int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
            dp0 = dp1; // 记录一下前两位
            dp1 = dpi;
        }
        return dp1;
    }
};

整数拆分

整数拆分

dp[n] 的值即为将正整数 n拆分成至少两个正整数的和之后，这些正整数的最大乘积

class Solution {
public:
    int integerBreak(int n) {
        vector <int> dp(n + 1);
        for (int i = 2; i <= n; i++) {
            int curMax = 0; 
            // 对正整数 i 拆分出的第一个正整数是 j
            for (int j = 1; j < i; j++) { 
            	// 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
				//将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
                curMax = max(curMax, max(j * (i - j), j * dp[i - j])); // dp[0] = dp[1] =0
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
};

最大子数组和（Hot 100）

最大子数组和

class Solution {  
public:  
    int maxSubArray(vector<int>& nums) {  
        // dp[i]: 以 nums[i] 结尾的连续子数组的最大和  
        vector<int> dp(nums.size());  
        dp[0] = nums[0]; // 初始情况，只有一个元素，最大和就是它本身  
        int maxSum = dp[0]; // 用来记录全局的最大和  
        for(int i = 1; i < nums.size(); i++){  
            // 对于第 i 个元素，考虑两种情况：  
            // 1. 要么单独作为一个子数组（值为 nums[i]）  
            // 2. 要么和前面的子数组组合（值为 dp[i-1] + nums[i]）  
            // 取两种情况中的较大值作为 dp[i]  
            dp[i] = max(nums[i], dp[i-1] + nums[i]);  
            // 同时更新全局最大和  
            maxSum = max(maxSum, dp[i]);  
        }  
        return maxSum; // 返回全局最大和  
    }  
};

背包问题系列

对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

背包问题二维dp变一维

二维DP：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

在二维数组中，dp[i][j] 依赖于 dp[i-1][j] 和 dp[i-1][j-weight[i]]，这两个状态都是上一行的数据。如果我们可以确保在更新 dp[i][j] 时，dp[i-1][…] 的值已经被计算出来且不会被覆盖【如何保证？】，那么可以把上一层 dp[i-1] 这一层 拷贝的 dp[i]来 ：

dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

此时dp第i行的值与其他行无关，因此可以简化为一维DP：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

【如何保证？】二维dp中，右下角的值依赖上一层左上角的值。因此在遍历一维dp下一层（物品）时，需要保证左边的值仍然是上一层的，故需要从右向左覆盖。

void test_1_wei_bag_problem() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    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]); // 尝试装入i提高dp
        }
    }
    cout << dp[bagWeight] << endl;
}

int main() {
    test_1_wei_bag_problem();
}

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。（类似于d[j] = max(d[j], d[j-1])）

dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。

分割等和子集(Hot 100，0-1背包)

分割等和子集

dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(10001, 0);
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
            sum += nums[i];
        if(sum % 2 == 1) return false;
        int target = sum / 2;
        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]);
        }
        if(dp[target] == target) return true;
        return false;
    }
    
};

完全平方数(Hot 100,完全背包)

完全平方数
0-1背包：每种物品只能取一个。
完全背包：每种物品的数量是无限的，可以重复选择

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        // dp[i]：和为i的完全平方数的最少数量为dp[i]
        for(int i = 0; i <= n; i++){ // 背包
            for(int j = 1; j*j <= i; j++) // 物品
                dp[i] = min(dp[i - j*j] + 1, dp[i]);
                // dp[i - j*j] + 1: i-j*j +j*j
                // dp[i]
        }
        return dp[n];
    }
};

单词拆分(Hot 100,完全背包)

单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict)  wordDictSet.insert(word);

        // dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词
        auto dp = vector <bool> (s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {  // 背包
            for (int j = 0; j < i; ++j) {   // 物品
                // 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};

零钱兑换（Hot 100，完全背包）

零钱兑换

// dp[j]:凑成金额j所需的 最少的硬币个数
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]); // 装入物品i or 不装入物品i
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

打家劫舍系列

打家劫舍（Hot 100）

打家劫舍

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        if(nums.size() == 1) return nums[0];
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2; i < nums.size(); i++)
            dp[i] = max(dp[i - 2] + nums[i], dp[i-1]);
        return dp[nums.size() - 1];
    }
};

子序列系列

最长递增子序列（Hot 100）

最长递增子序列

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {

        // 设nums[i]最长严格递增子序列的长度dp[i]
        vector<int>dp(nums.size(),1);
        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < i; j++){ 
                if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j] + 1);// j中的最大值
            }
            ans = max(ans, dp[i]); // i中的最大值
        }
        return ans;

    }
};

多维动态规划

不同路径（Hot 100）

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++) dp[i][0] = 1;
        for(int j = 0; j < n; j++) dp[0][j] = 1;
        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];
    }
};

不同路径 II

不同路径 II

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++)
            dp[i][0] = 1;
        for(int j = 0; j < n && obstacleGrid[0][j] ==0 ;j++)
            dp[0][j] = 1;
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
};

最小路径和（Hot 100）

最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int rows = grid.size(), columns = grid[0].size();
        auto dp = vector < vector <int> > (rows, vector <int> (columns));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
};

最长回文子串（Hot 100）

最长回文子串

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2)  return s;
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(s.size(), vector<int>(s.size()));

        // 先枚举子串长度
        for (int length = 1; length <= s.size(); length++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < s.size(); i++) {
                // 所有长度为 length= 1 的子串都是回文串
                if(length == 1) dp[i][i] = true;
                else{
                    // 由 length 和 i 可以确定右边界，即 j - i + 1 = length 得
                    int j = length + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= s.size())  break;
                    // 长度小于等于3，只要两端字符相同，就是回文的
                    // 长度大于3，还需要中间为回文串
                    if (length <= 3) dp[i][j] = (s[i] == s[j]); 
                    else dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);  

                    // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，
                    // 此时记录回文长度和起始位置
                    if (dp[i][j] && length > maxLen) {
                        maxLen = length;
                        begin = i;
                    }
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

最长公共子序列（Hot 100）

最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // dp[i][j] text1[0:i-1]和text2[0:j-1]的最长公共子序列长度
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        for(int i = 1; i <= text1.size(); i++){
            for(int j = 1; j <= text2.size(); j++){
                if(text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i][j-1],max(dp[i-1][j-1],dp[i-1][j]));
            }
        }
        return dp.back().back();

    }
};

编辑距离 （Hot 100）

编辑距离

// https://leetcode.cn/problems/edit-distance/solutions/189676/edit-distance-by-ikaruga/
class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数，dp[0][0]为空
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i < dp.size(); i++) dp[i][0] = i;

        for (int j = 0; j < dp[0].size(); j++) dp[0][j] = j;
   

        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].size(); j++) {

                if (word1[i - 1] == word2[j - 1]) { // 当前字母相同，注意索引是+1的，所以得减1
                    dp[i][j] = dp[i - 1][j - 1]; 
                }else{
                    // 改、删或增 abc -> 123
                	dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    // 改  dp[i - 1][j - 1]:  'ab' - > '12'的次数；dp[i][j]: ‘abc’ ->'12c'-改> '123' 
                    // 增 dp[i][j - 1]: 'abc' -> '12'的次数   dp[i][j]: 'abc' -> '12'-增>'123'
                    // d[i-1][j]: 'ab' -> '123'的次数   dp[i][j]:  'abc' -删>‘ab’ -> '123'

                }
            }
        }
        return dp.back().back();
    }
};

其他

乘积最大子数组（Hot 100）

乘积最大子数组

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector <long> maxF(nums.begin(),nums.end()), minF(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i) {
            maxF[i] = max(maxF[i - 1] * nums[i], max((long)nums[i], minF[i - 1] * nums[i]));
            minF[i] = min(minF[i - 1] * nums[i], min((long)nums[i], maxF[i - 1] * nums[i]));
            if(minF[i]<INT_MIN) {
                minF[i]=nums[i];
            }
        }
        return *max_element(maxF.begin(), maxF.end());
    }
};

最长有效括号(Hot 100)

最长有效括号

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;            // 变量用于存储最长有效括号的长度
        stack<int> stk;            // 栈用于存储字符的索引
        stk.push(-1);              // 初始化栈，压入 -1 以处理基础情况
        
        // 遍历字符串
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {     // 如果当前字符是 '('
                stk.push(i);       // 将当前索引压入栈中
            } else {               // 如果当前字符是 ')'
                stk.pop();         // 弹出栈顶元素，尝试匹配一个 '('
                if (stk.empty()) { // 如果栈为空，说明没有匹配的 '('
                    stk.push(i);   // 将当前索引压入栈，作为新的基准点
                } else {
                    // 如果栈不为空，计算当前有效括号长度
                    maxans = max(maxans, i - stk.top());
                }
            }
        }
        return maxans;             // 返回最长的有效括号长度
    }
};