算法刷题 - LC101の6. DP - 《动手敲敲》

title: LC101の6. DP
urlname: fth98y
date: ‘2021-06-18 19:50:06’
tags: [DP]
categories: [算法刷题]

简介

动态规划（DP）将问题拆分成多个子问题，保存子问题的解以避免重复计算。
解决 DP 问题的关键在于找到状态转移方程。
可以通过对动态规划进行空间压缩起到节省空间消耗的效果。

基本动态规划：一维

70. 爬楼梯

题目大意：给定 n 节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。
输入：n = 2 输出：2

解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
思路：简单斐波那契数列

int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1, 1);
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

198. 打家劫舍

题目大意：假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果
你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。
输入：[1,2,3,1] 输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
思路：用 dp[i]表示抢劫到第 i 个房子前，可抢劫的最大数量，因此得到状态转移方程 dp[i] = max(dp[i-1],
nums[i-1] + dp[i-2])

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

413. 等差数列划分

题目大意：给定一个数组，求这个数组中连续且等差的子数组一共有多少个。
输入：nums = [1,2,3,4] 输出：3

解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
思路：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return 0;
    vector<int> dp(n, 0);
    for (int i = 2; i < n; ++i) {
    if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
        dp[i] = dp[i-1] + 1;
    } }
    return accumulate(dp.begin(), dp.end(), 0);
    }
};

基本动态规划：二维

64. 最小路径和

题目大意：给定一个 m × n 大小的非负整数矩阵，求从左上角开始到右下角结束的、经过的数字的和最
小的路径。每次只能向右或者向下移动。
LC101の6. DP - 图1
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0){
                    dp[i][j] = grid[i][j];
                }else if(i == 0){
                    //只能往下走
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }else if(j == 0){
                    //只能往右走
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                }else{
                    //比较下和右
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

542. 01 矩阵

题目大意：给定一个由 0 和 1 组成的二维矩阵，求每个位置到最近的 0 的距离。
LC101の6. DP - 图2
输入：mat = [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]]
**思路：对每个位置进行四向搜索，会达到恐怖的 O(m2n2)。因此，从左上到右下，从右下到左上分别进行一次。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX - 1));
        // 从左上角开始
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(mat[i][j] == 0){
                    dp[i][j] = 0;
                }else{
                    if (i > 0) {
                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
                    }
                    if (j > 0) {
                        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
                    }
                }
            }
        }
        // 从右下角开始
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i + 1 < m) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
                }
            }
        }
        return dp;
    }
};

题目大意：给定一个二维的 0-1 矩阵，求全由 1 构成的最大正方形面积。
LC101の6. DP - 图3
输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：4
思路：dp(i, j) 表示以 (i, j)为右下角，且只包含 1 的正方形的边长最大值
如果该位置的值是 0，则 dp(i, j) = 0，因为当前位置不可能在由 1 组成的正方形中；
如果该位置的值是 1，则 dp(i, j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：
dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        if(n == 0 || m == 0) return 0;
        vector<vector<int>> dp(n,vector<int>(m));
        int maxSide = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};

分割类问题

279. 完全平方数

题目大意：整数 n ，返回和为 n 的完全平方数的最少数量。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j * j <= i; j++){
                dp[i] = min(dp[i], dp[i - j*j] + 1);
            }
        }
        return dp[n];
    }
};

91. 解码方法

题目大意：编码规则：’A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26”，
给出已编码的数字串，返回解码前字母组成的情况数。
LC101の6. DP - 图4

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        int pre = 1, curr = 1;//dp[-1] = dp[0] = 1
        for (int i = 1; i < s.size(); i++) {
            int tmp = curr;
            if (s[i] == '0')
                if (s[i - 1] == '1' || s[i - 1] == '2') curr = pre;
                else return 0;
            else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6'))
                curr = curr + pre;
            pre = tmp;
        }
        return curr;
    }
};

子序列问题

300. 最长递增子序列

题目大意：求最长递归子序列
思路：技巧就是用 dp[i] 表示 以 i 结尾的、最长子序列长度

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

1143. 最长公共子序列

题目大意：求最长公共子序列
思路：技巧就是 dp[i，j]表示子串 str1[0…i-1]，str[0…j-1]的最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        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];
    }
};

背包问题

背包问题是一种组合优化的 NP 完全问题：有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

普通背包：

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = 1; j <= W; ++j) {
            if (j >= w) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

空间优化

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = W; j >= w; --j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}

完全背包：

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = 1; j <= W; ++j) {
            if (j >= w) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

空间优化

int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = w; j <= W; ++j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}

416. Partition Equal Subset Sum

字符串编辑

72. 编辑距离

题目大意：输入两个字符串 s1,s2，输出最少步骤（插入，删除，修改）使 s1==s2
思路：用 dp[i][j]表示只取 s1 前 i 位和 s2 前 j 位，需要的最少步骤。
不改是 dp[i-1][j-1]，修改是 dp[i-1][j-1]+1，插入 i 删除 j 是 dp[i][j-1]+1，插入 j 删除 i 是 dp[i-1][j]+1，比对最小值

class Solution {
    public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for(int i = 0; i <= len1; i++){
            for(int j = 0; j <= len2; j++){
                if(i == 0){
                    dp[i][j] = j;
                }else if(j == 0){
                    dp[i][j] = i;
                }
                else{
                    dp[i][j] = min(dp[i-1][j-1] + ((word1[i-1] == word2[j-1])? 0: 1),min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }
            }
        }
        return dp[len1][len2];
    }
};

650. 只有两个键的键盘

题目大意：给定字母 A，只可以复制全部或粘贴，求最少几次到指定长度
思路：用 dp[i]表示到 i 位置的最少次数，对于 j 位置，如果 j 可以被 i 整除，就相当于在 dp[j]的基础上进行粘贴，dp[i] = dp[j] + dp[i/j]

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        for (int i = 2; i <= n; ++i) {
            dp[i] = i;
            for (int j = 2; j <= sqrt(n); ++j) {
                if (i % j == 0) {
                    dp[i] = dp[j] + dp[i/j];
                    break;
                }
            }
        }
        return dp[n];
    }
};

10. 正则表达式匹配

题目大意：字符串 a 是否满足正则表达式 b（只有字母和 . 和）
*思路：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i < n + 1; ++i) {
            if (p[i-1] == '*') {
                dp[0][i] = dp[0][i-2];
            }
        }
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                if (p[j-1] == '*') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p[j-1] != '*') {
                    dp[i][j] = dp[i-1][j-1] && p[j-1] == s[i-1];
                } else if (p[j-2] != s[i-1] && p[j-2] != '.') {
                    dp[i][j] = dp[i][j-2];
                } else {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2];
                }
            }
        }
        return dp[m][n];
    }
};

股票交易

这个买票股票系列 LeetCode101 中省略了三道，手动补充完整

额外参考：股票问题系列

121. 买卖股票的最佳时机

题目大意：给定股票每天的价格，只能买卖一次，求最大收益
思路：遍历，维护两个值，最大收益 = max 当前价格 - 左边最小价格，最小价格 = min 左边最小价格

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = 1e9, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

动手敲敲

LC101の6. DP

简介