Skip to content

Latest commit

 

History

History
613 lines (476 loc) · 17.2 KB

11_dp.md

File metadata and controls

613 lines (476 loc) · 17.2 KB

动态规划

(1) 常用技巧总结

动态规划在面试中占据了绝对的重要的地位，值得重点突破。下面是动态规划解题的基本步骤：

（1） 确定状态: 确定 $dp[i]$ 代表什么 ? 可以从考虑子问题和最后一步进行考虑

（2） 确定转移方程 $dp[i] = f(dp[i-1])$

（3）初始条件和边界情况：起始值的赋值 & 最后一步

（4） 计算顺序: 消除冗余，加速计算 $f[0], f[1], f[2], ... $

常用技巧：

  • 如何确定某个题目是动态规划类的题目:

    • count 计数：有多少种方式走到右下角、有多少种方式选出 k 个数使得和是 sum

    • min/max求最大最小值：从左上角到右下角路径的最大数字和、最长上升子序列长度

    • yes/no 求存在性：取石子游戏， 先手是否必胜、能不能选出k个数使得和是Sum

  • 对于字符串的相关问题(回文、公共子串、上升子串)， 一个很常见的操作就是，用字符串构造矩阵，然后进行状态转移。

  • 解题步骤中：确定状态和确定转移方程是最重要的。

  • 没有思路的时候可以从起始状态进行模拟，或者取其中一个特殊的状态进行模拟。

(2) 典型例题

类型一 简单一维 DP
[509] 斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/
// 使用 prev 和 cur 来消除了 DP 数组的使用
int fib(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    int prev = 0, cur = 1;
    for(int i = 2; i <= n; i++){
        int s = (prev + cur) % 1000000007;
        prev = cur;
        cur = s;
    }
    return cur;
}
[70] 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/
int numWays(int n) {
    if(n <= 1) return 1;
    if(n == 2) return 2;
    int prev = 1, cur = 2;
    for(int i = 3; i <= n; i++){
        int s= (prev + cur) % 1000000007;
        prev = cur;
        cur = s;
    }
    return cur;
}
[198] https://leetcode.com/problems/house-robber/
int rob(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    if(nums.size() == 1) return nums[0];
    if(nums.size() == 2) return max(nums[0], nums[1]);

    vector<int > dp(nums.size(), 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    int res = 2;
    for(int i = 2; i < nums.size(); i++){
        // 转移方程只和前两个状态有关:
        // (1) 选择当前的房子: dp[i-2] + nums[i]
        // (2) 不选当前房子: dp[i-1]
        dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[nums.size()-1];
}
[264] https://leetcode-cn.com/problems/ugly-number-ii/ 🌟🌟🌟
// 其实就是不断的求数组 A， B， C 的最小值
// A: {1*2，2*2，3*2，4*2，5*2，6*2，8*2，10*2......}
// B: {1*3，2*3，3*3，4*3，5*3，6*3，8*3，10*3......}
// C: {1*5，2*5，3*5，4*5，5*5，6*5，8*5，10*5......}
int nthUglyNumber(int n) {
    vector<int> dp(n, 0);
    dp[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0; // 这里是三个指针，分别指向三个数组
    for(int i = 1; i < n; i++){
        // 只和之前的三个变量有关系
        dp[i] = min(min(dp[p2]*2, dp[p3]*3), dp[p5]*5);  
        if(dp[i]/dp[p2] == 2) p2++;
        if(dp[i]/dp[p3] == 3) p3++;
        if(dp[i]/dp[p5] == 5) p5++;
    }
    return dp[n-1];
}
[53] 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/ 🌟🌟
int maxSubArray(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    int res = nums[0];
    // 以 dp 为结束的最大子序列的和
    vector<int> dp(nums.size(), 0); 
    dp[0] = nums[0];

    for(int i = 1; i < nums.size(); i++){
        dp[i] = dp[i-1] > 0 ? dp[i-1] + nums[i] : nums[i];
        res = max(res, dp[i]);
    }
    return res;
}

// 这道题和上面那道几乎相同: dp[i] 的定义类似，转移方程也类似
类型二 一维 DP： 与之前的所有的 dp 状态均有关系

接下来几道题目虽然形式各异，但是当前的状态和之前的所有状态均有联系。

[lcof 14- I] 剪绳子 https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
int cuttingRope(int n) {
    if(n <= 3) return n-1;

    // dp[n] 表示长度为 n 的绳子，剪成若干段之后，乘积的最大值
    vector<int> dp(n+1, 1);
    // 如果某个长度的绳子，剪了一下之后，其中一段的长度在 [0,3] 的区间内，就不要再剪这一段了
    // 因为剪了之后，乘积会变小
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

    for(int i = 4;  i <= n; i++){   // 逐渐增加 dp 数组的长度 
        for(int j = 1; j <= i / 2; j++){     // 第一刀剪在什么地方?
            //  剩下的两段为 j 和 i-j， 求这两段的最大值即可
            dp[i] = max(dp[i], dp[j] * dp[i-j]);
        }
    }
    return dp[n];
}
[300]. 最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/) 🌟🌟🌟
// 核心思想：
// 当 nums[j] > nums[i] 时： nums[j] 可以接在 nums[i] 之后，此情况下最长上升子序列长度为 dp[i] + 1 ；
// 否则 无法接在 nums[i]之后，此情况上升子序列不成立，跳过。
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) return 0;

    vector<int> dp(n, 1);

    dp[0] = 1;
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(nums[j] > nums[i])
                dp[j] = max(dp[j], dp[i]+1);
        }
    }
    return *max_element(dp.begin(), dp.end());
}
[354] 俄罗斯套娃信封问题 (https://leetcode-cn.com/problems/russian-doll-envelopes/)
// 先将信封按照第一个元素升序，第二个元素降序进行排列， 然后求所有第二个元素的最长递增子序列
int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](vector<int> a, vector<int> b){
        return (a[0] < b[0]) || (a[0] == b[0] && a[1] > b[1]);
    });
    
    vector<int> nums;
    for(auto envelope: envelopes) nums.push_back(envelope[1]);
    return lengthOfLIS(nums);
}

接下来这两道题目虽然没有直接的 dp 形式，但是蕴含的 dp 思想，而且是可以写成 dp 的。

[152] 乘积最大子数组 https://leetcode-cn.com/problems/maximum-product-subarray/
// 这个题目是 dp 的思想在解决， 但是不是用的 dp
// 维持一个最大值和一个最小值的数组
int maxProduct(vector<int>& nums) {
    int res = INT_MIN;
    int min_val = 1, max_val = 1;
    for(auto n:nums){
        if(n < 0) swap(max_val, min_val);  // 如果当前值小于零，则对最大值和最小值进行互换
        min_val = min(min_val * n, n);
        max_val = max(max_val * n, n);

        res = max(res, max_val);
    }
    return res;
}
[376] 摆动序列 https://leetcode-cn.com/problems/wiggle-subsequence/ 🌟🌟
// 思路参考: https://leetcode-cn.com/problems/wiggle-subsequence/solution/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/
int wiggleMaxLength(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    int up = 1, down = 1;

    for(int i = 1;  i < nums.size(); i++){
        if(nums[i] > nums[i-1]) up = down + 1;
        else if(nums[i] < nums[i-1]) down = up + 1;
    }
    return max(up, down);
}
类型三： 二维 DP
[62] 不同路径 https://leetcode-cn.com/problems/unique-paths/
int uniquePaths(int m, int n) {
    vector<vector<int> > dp(m, vector<int>(n, 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];
}
[63] 不同路径 II https://leetcode-cn.com/problems/unique-paths-ii/ 🌟🌟
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if(obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0) return 0;
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int> > dp(m, vector<int>(n, 1));

    dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    for(int i = 1; i < m; i++)  dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
    for(int j = 1; j < n; j++)  dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];

    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}
[64] 最小路径和 https://leetcode-cn.com/problems/minimum-path-sum/
int minPathSum(vector<vector<int>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0) return 0;
    int m = grid.size();
    int n = grid[0].size();

    vector<vector<int> > dp(m, vector<int>(n, 0));
    
    dp[0][0] = grid[0][0];
    for(int i = 1; i < n; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
    for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];

    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}
[lcof 47] https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
int maxValue(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int> > dp(m, vector<int>(n));   // 这个语法使用错了  vector

    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for(int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}
[120] 三角形最小路径和 https://leetcode-cn.com/problems/triangle/
// 直接在原数组上更改
int minimumTotal(vector<vector<int>>& triangle) {
    if(triangle.size() == 0 || triangle[0].size() == 0) return 0;
    int n = triangle.size();

    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0) triangle[i][0] = triangle[i-1][0] + triangle[i][j];
            else if(j == i) triangle[i][i] = triangle[i-1][i-1] + triangle[i][j];
            else{
                triangle[i][j] = min(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j];
            }
        }
    }

    int res = INT_MAX;
    for(int i = 0; i < n; i++)  res = min(res, triangle[n-1][i]);
    return res;
}
类型四： 子串和子序列问题：上升、摆动、回文、公共

这些题目的共同解法是以其中一个字符作为行， 另一个字符作为列， 然后创建二维数组进行遍历。

  • 最长公共子串/子序列
[718] 最长重复子数组 https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
int findLength(vector<int>& A, vector<int>& B) {
    int res = 0;
    int m = A.size(), n = B.size();
    vector<vector<int> > dp(m, vector<int>(n, 0));

    // init
    for(int i = 0; i < m; i++) 
        if(A[i] == B[0]) dp[i][0] = 1;
    
    for(int i = 0;  i < n; i++)
        if(A[0] == B[i]) dp[0][i] = 1;

    // transform
    for(int i = 1; i < m; i++){
        for(int j = 1;  j < n; j++){
            if(A[i] == B[j]) 
                dp[i][j] = dp[i-1][j-1] + 1;
                res = max(res, dp[i][j]);
        }
    }
    return res;
}
[1143] 最长公共子序列 https://leetcode-cn.com/problems/longest-common-subsequence/ 🌟🌟🌟
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();

    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));

    for(int i = 1; i <= m; i++){
        for(int j = 1; j<= n; j++){
            // 因为矩阵大小为 (m+1)(n+1),  所以 i-1, j-1 对应的 dp的 i,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[m][n];
}
  • 最长回文子串/子序列
[5] 最长回文子串 https://leetcode-cn.com/problems/longest-palindromic-substring/ 🌟🌟
string palindrome(string str, int i, int j, int base){
    for(;i >= 0 && j < str.size() && str[i] == str[j]; i--, j++)   len += 2;
    return str.substr(i+1, base);

}

string longestPalindrome(string s) {
    string res = "";
    if(s.size() == 1) return s;

    string s1, s2;
    for(int i = 1; i < s.size(); i++){
        s1 = palindrome(s, i-1, i+1, 1);
        s2 = palindrome(s, i-1, i, 0);
        string max_str = s1.size() > s2.size() ? s1 : s2;
        res = res.size() > max_str.size() ? res : max_str;
    }
    return res;
}
[516] 最长回文子序列 https://leetcode-cn.com/problems/longest-palindromic-subsequence/ 🌟🌟🌟
int longestPalindromeSubseq(string s) {

    int n = s.size();
    vector<vector<int> > dp(n, vector<int>(n));

    // dp[i][j]: j->i 最大回文子串的长度
    for(int i = 0; i < n; i++) dp[i][i] = 1;

    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];
}
[583] 两个字符串的删除操作 https://leetcode-cn.com/problems/delete-operation-for-two-strings/
int minDistance(string word1, string word2) {
    // 可以转换为求公共子串的问题
    if(word1.size() == 0 || word2.size() == 0) return 0;
    
    int m = word1.size();
    int n = word2.size();

    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(word1[i-1] == word2[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 m + n - 2*dp[m][n];
}
[72] 编辑距离 https://leetcode-cn.com/problems/edit-distance/ 🌟🌟🌟
int minDistance(string word1, string word2) {
    if(word1.size() == 0) return word2.size();
    if(word2.size() == 0) return word1.size();

    int m = word1.size(), n = word2.size();
    vector<vector<int> > dp(m+1, vector<int>(n+1, 0));

    dp[0][0] = 0;
    for(int i = 1; i <= m; i++)   dp[i][0] = i;
    for(int j = 1; j <= n; j++) dp[0][j] = j;

    for(int i = 1;  i <= m; i++){
        for(int j = 1; j <= n; 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[m][n];
}
类型五: 股票交易

股票交易问题主要包括以下几道题目： 原始的买卖股票121、无限次操作122、只能进行两次操作123、最多 k 次188、含冷冻期 309、含手续费 714

[121] 买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 🌟🌟🌟
// 寻找 vector 的最小值，用后面的值减去之前的最小值
int maxProfit(vector<int>& prices) {
    int min_val = INT_MAX;
    int max_profit = 0;

    for(int i = 0; i < prices.size(); i++){
        min_val = min(min_val, prices[i]);
        max_profit = max(max_profit, prices[i] - min_val);
    }
    return max_profit <=0 ? 0 : max_profit;

}
[122] 买卖股票的最佳时机
// 第 i 天的收益为 profit = prices[i] - prices[i-1]
//（1）当 profit > 0 时，当天买入卖出
//（2）当 profit <= 0 时，当天不进行交易
int maxProfit(vector<int>& prices) {
    int profit = 0;
    if(prices.size() <= 1) return 0;
    for(int i = 1; i < prices.size(); i++){
        if(prices[i] > prices[i-1])
            profit += (prices[i] - prices[i-1]);
    }
    return profit;
}
类型七： 分割整数
[343] https://leetcode-cn.com/problems/integer-break/ 🌟🌟
int cuttingRope(int n) {
    if(n == 2) return 1;
    if(n == 3) return 2;

    int mod = (int)1e9 + 7;
    long res = 1;
    // 当大于 4 时候， 优先剪成 3, 之后乘以剩下的一段
    while(n > 4){
        res *= 3;
        res %= mod;
        n-=3;
    }
    res = (n * res) % mod;
    return res;  
}
其他
[lcof46] https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/ 🌟🌟
int translateNum(int num) {
    string str = to_string(num);
    int n = str.size();

    // dp[i] 表示前 i 位 可以有几种翻译方法
    vector<int> dp(n + 1, 1);

    for(int i = 1; i < n; i++){
        // 如果前一个是 0， 或者 前一个和当前 > 25， 那么不能组成一个新字母
        if (str[i-1] == '0' || str.substr(i-1, 2) > "25" ) {
            dp[i+1] = dp[i];
        } else {
            dp[i+1] = dp[i] + dp[i-1];
        }
    }

    return dp[str.size()];
}
类型三 背包问题
[322] 零钱兑换 https://leetcode-cn.com/problems/coin-change/ 🌟🌟🌟
int coinChange(vector<int>& coins, int amount) {
    //  dp[i]: 金额为i时候的最小使用张数 -> 初始化为 amount+1
    vector<int> dp(amount + 1, amount + 1);
    
    dp[0] = 0;
    for(int i = 1; i <= amount; i++){
        for(auto coin:coins){
            if(i >= coin)  dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}