入门 DP

爬楼梯

爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n+1);     
        f[0]=1,f[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }
};
/*由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)*/
class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

使用最小花费爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 0;
        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];
    }
};

组合总和 Ⅳ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*本质是爬楼梯，相当于每次往上爬 nums[i] 步*/
class Solution {
public:
    long long combinationSum4(vector<int>& nums, int target) {
        vector<long long> dp(target + 1);
        dp[0] = 1; //只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
        for (int i = 1; i <= target; i++) {
            for (int& num : nums) {
                if (num <= i&& dp[i - num] < INT_MAX - dp[i]) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};
/*另一种写法*/
class Solution {
public:
    int combinationSum4(vector<int> &nums, int target) {
        // 使用 unsigned 可以让溢出不报错
        // 对于溢出的数据，不会影响答案的正确性（题目保证）
        vector<unsigned> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i) {
                    f[i] += f[i - x];
                }
            }
        }
        return f[target];
    }
};

统计构造好字符串的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1'000'000'007;
        int ans = 0;
        vector<int> f(high + 1); // f[i] 表示构造长为 i 的字符串的方案数
        f[0] = 1; // 构造空串的方案数为 1
        for (int i = 1; i <= high; i++) {
            if (i >= zero) f[i] = f[i - zero];
            if (i >= one)  f[i] = (f[i] + f[i - one]) % MOD;
            if (i >= low)  ans = (ans + f[i]) % MOD;
        }
        return ans;
    }
};

统计打字方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int countTexts(string pressedKeys) {
        int m = 1000000007;
        vector<long long> dp3 = {1, 1, 2, 4};   // 连续按多次 3 个字母按键对应的方案数
        vector<long long> dp4 = {1, 1, 2, 4};   // 连续按多次 4 个字母按键对应的方案数
        int n = pressedKeys.size();
        for (int i = 4; i < n + 1; ++i) {
            dp3.push_back((dp3[i-1] + dp3[i-2] + dp3[i-3]) % m);
            dp4.push_back((dp4[i-1] + dp4[i-2] + dp4[i-3] + dp4[i-4]) % m);
        }
        long long res = 1;   // 总方案数
        int cnt = 1;   // 当前字符连续出现的次数
        for (int i = 1; i < n; ++i) {
            if (pressedKeys[i] == pressedKeys[i-1]) {
                ++cnt;
            } else {
                // 对按键对应字符数量讨论并更新总方案数
                if (pressedKeys[i-1] == '7' || pressedKeys[i-1] == '9') {
                    res *= dp4[cnt];
                } else {
                    res *= dp3[cnt];
                }
                res %= m;
                cnt = 1;
            }
        }
        // 更新最后一段连续字符子串对应的方案数
        if (pressedKeys[n-1] == '7' || pressedKeys[n-1] == '9') {
            res *= dp4[cnt];
        } else {
            res *= dp3[cnt];
        }
        res %= m;
        return res;
    }
};

打家劫舍

打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*题意转化为：从序列中选择子序列使得它们的和最大，数不能有相邻*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return nums[0];
        vector<int> dp(n,0); //用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }  
        return dp[n-1];
    }
};
/*上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return nums[0];
        int first=nums[0],second=max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            int temp=second;
            second=max(first+nums[i],second);
            first=temp;
        }
        return second;
    }
};

删除并获得点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return nums[0];
        int first=nums[0],second=max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            int temp=second;
            second=max(first+nums[i],second);
            first=temp;
        }
        return second;
    }
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxval=0;
        for(int val:nums){
            maxval=max(maxval,val);
        }
        vector<int>sum(maxval+1,0);
        for(int val:nums){
            sum[val]+=val;
        }
        return rob(sum);
    }
};

统计放置房子的方式数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*单独考虑一侧的房子，定义 f[i] 表示前 i 个地块的放置方案数，其中第 i 个地块可以放房子，也可以不放房子。*/
const int mod=1e9+7;
class Solution {
public:
    int countHousePlacements(int n) {
        vector<long long> f(n+1,0);
        f[0]=1;
        f[1]=2;
        for(int i=2;i<=n;i++){
            f[i]=(f[i-1]+f[i-2])%mod;
        }
        return f[n]*f[n]%mod;
    }
};

打家劫舍 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*第一间房屋和最后一间房屋不同时偷窃*/
class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int first = nums[start], second = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

    int rob(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) {
            return nums[0];
        } 
        else if (length == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
};

施咒的最大总伤害

最大子数组和

定义状态 f[i] 表示以 a[i] 结尾的最大子数组和，不和 i 左边拼起来就是f[i]=a[i]，和 i 左边拼起来就是f[i]=f[i−1]+a[i]，取最大值就得到了状态转移方程 f[i]=max(f[i−1],0)+a[i]，答案为 max(f)。这个做法也叫做 Kadane 算法。

最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
/*模板题*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1],0)+nums[i];
        }
        return ranges::max(dp);
    }
};

找到最大开销的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*一点转化+模板题*/
class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        vector<int> m(26+1);
        iota(m.begin(),m.end(),0);
        for(int i=0;i<chars.size();i++){
            m[chars[i]-'a'+1]=vals[i];
        }
 
        vector<int> dp(s.size());
        dp[0]=m[s[0]-'a'+1];
        int ans=max(0,dp[0]);
        for(int i=1;i<s.size();i++){
            dp[i]=max(dp[i-1],0)+m[s[i]-'a'+1];
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

任意子数组和的绝对值的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*题目转化为max(最大子数组和，-最小子数组和，0)*/
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        int ans1=dp[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1],0)+nums[i];
            ans1=max(ans1,dp[i]);
        }
 
        vector<int> dp1(nums.size());
        dp1[0]=nums[0];
        int ans2=dp1[0];
        for(int i=1;i<nums.size();i++){
            dp1[i]=min(dp1[i-1],0)+nums[i];
            ans2=min(ans2,dp1[i]);
        }
        int ans=max(0,ans1);
        ans=max(ans,-ans2);
        return ans;
    }
};

K 次串联后最大子数组之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
考虑两种情况：

1.如果k=1，那就是正常DP。

2.k>1时也考虑两种情况：数组所有元素和大于0，数组所有元素和小于等于0。
首先计算两个相接的DP也就是k=2的情况，如果数组元素和大于0，那可以看成再第一段结尾第二段开头插入k-2个正数，如果数组所有元素和为负，那k=2的情况就是最大的情况。
*/
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        const int mod=1e9+7;
        int n=arr.size();
        long long sum=0,presum=0,result=0;
        for(int i=0;i<n*(k>1?2:1);i++){
            long long num=arr[i%n];
            presum=max(presum,0ll)+num;
            result=max(result,presum);
            if(i<n) sum+=num;
        }
        if(sum>0&&k>1){
            result=(result+sum*(k-2)%mod)%mod;
        }
        return result;
    }
};
/*
1.sum>0、k=2时，最大子数组和如果没有跨过两个数组，那岂不是不能在中间插入k-2个sum吗？
反证法，反设sum>0时，如果最大子数组和没有跨过两个数组。从L到R的子数组的和最大（0<=L<=R<n-1），考虑R向右n个数(R+1到R+n)，这n个数一定是和arr的数是一样的（循环了），那么这n个数的和是sum，大于0。所以从L到R+n的子数组的和要更大，而这个子数组跨过了两个数组，与反设矛盾。所以这样做是对的。
2.sum<=0时，为什么可以化归到k=2的情况？
还是反证法，假设最大子数组的长度>2n，那一定包括一个完整的arr数组，那么因为sum<=0，所以拿掉这一部分，把前后拼接在一起（这样做显然是合法的），这样做结果只会更优，如此操作下去，就可以划归到k=2的情况了。
*/

环形子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n=nums.size();
        vector<int> qianmax(n); //前缀最大值
        int presum=nums[0];
        qianmax[0]=nums[0];

        int pre=nums[0];
        int ans=pre;

        for(int i=1;i<n;i++){
            pre=max(pre,0)+nums[i];
            ans=max(ans,pre);

            presum+=nums[i];
            qianmax[i]=max(qianmax[i-1],presum);
        }

        int housum=0;
        for(int i=n-1;i>0;i--){ //枚举后缀和
            housum+=nums[i];
            ans=max(ans,housum+qianmax[i-1]);
        }
        return ans;
    }
};

拼接数组的最大分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*转换成最大子数组和*/
class Solution {
    int solve(vector<int> &nums1, vector<int> &nums2) {
        int sum = 0, maxSum = 0;
        for (int i = 0, s = 0; i < nums1.size(); i++) {
            sum += nums1[i];
            s = max(s,0)+(nums2[i] - nums1[i]);
            maxSum = max(maxSum, s);
        }
        return sum + maxSum;
    }

public:
    int maximumsSplicedArray(vector<int> &nums1, vector<int> &nums2) {
        return max(solve(nums1, nums2), solve(nums2, nums1));
    }
};

(扩展）乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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());
    }
};
/*优化空间*/
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        long maxF = nums[0], minF = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            long mx = maxF, mn = minF;
            maxF = max(mx * nums[i], max((long)nums[i], mn * nums[i]));
            minF = min(mn * nums[i], min((long)nums[i], mx * nums[i]));
            if(minF<INT_MIN) {
                minF=nums[i];
            }
            ans = max(maxF, ans);
        }
        return ans;
    }
};

网格图 DP

基础

珠宝的最高价值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n=frame.size();
        int m=frame[0].size();
        vector<vector<int>> f(n,vector<int>(m));
        f[0][0]=frame[0][0];
        for(int i=1;i<n;i++){ //处理第一列
            f[i][0]=f[i-1][0]+frame[i][0];
        }
        for(int j=1;j<m;j++){ //处理第一行
            f[0][j]=f[0][j-1]+frame[0][j];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+frame[i][j];
            }
        }
        return f[n-1][m-1];
    }
};
 
/*注意到状态转移方程中，f(i,j) 只会从 f(i−1,j) 和 f(i,j−1) 转移而来，而与 f(i−2,⋯) 以及更早的状态无关，因此我们同一时刻只需要存储最后两行的状态，即使用两个长度为 n 的一位数组代替 n×m 的二维数组 f，交替地进行状态转移，减少空间复杂度。*/
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n=frame.size();
        int m=frame[0].size();
        vector<vector<int>> f(2,vector<int>(m));
        for(int i=0;i<n;i++){
            int pos=i%2;
            for(int j=0;j<m;j++){
                f[pos][j]=0;
                if(i>0) f[pos][j]=max(f[pos][j],f[1-pos][j]);
                if(j>0) f[pos][j]=max(f[pos][j],f[pos][j-1]);
                f[pos][j]+=frame[i][j];
            }
        }
        return f[(n-1)%2][m-1];
    }
};

不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m,vector<int>(n));
        for(int i=0;i<m;i++) f[i][0]=1;
        for(int j=0;j<n;j++) f[0][j]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};
/*此外，由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。*/
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> f(n,1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[j]+=f[j-1];
            }
        }
        return f[n - 1];
    }
};

不同路径 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> f(m,vector<int>(n));
        for(int i=0;i<m;i++){ //处理第一列
            if(obstacleGrid[i][0]==1){ //有障碍 
                f[i][0]=0; 
                break; //后面都到达不了
            }
            else f[i][0]=1;
        }
        for(int j=0;j<n;j++){  //处理第一行
            if(obstacleGrid[0][j]==1){ //有障碍
                f[0][j]=0; 
                break; //后面都到达不了
            }
            else f[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==1) f[i][j]=0;
                else f[i][j]=f[i-1][j]+f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};

最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<int>> dp(n,vector<int>(m));
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++) dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int j=1;j<m;j++) dp[0][j]=dp[0][j-1]+grid[0][j];
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};

三角形最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(n,vector<int>(n));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i-1][0]+triangle[i][0]; //第一列只能从上面转移
            for(int j=1;j<i;j++){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i][j];
            }
            dp[i][i]=dp[i-1][i-1]+triangle[i][i];//最后一列只能从左上转移
        }
        return *min_element(dp[n-1].begin(),dp[n-1].end());
    }
};
/*可以发现，dp[i][j] 只与 dp[i−1][..] 有关，而与 dp[i−2][..] 及之前的状态无关，因此我们不必存储这些无关的状态。具体地，我们使用两个长度为 n 的一维数组进行转移，将 i 根据奇偶性映射到其中一个一维数组，那么 i−1 就映射到了另一个一维数组。这样我们使用这两个一维数组，交替地进行状态转移。*/
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n=triangle.size();
        vector<vector<int>> dp(2,vector<int>(n));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<n;i++){
            int cur=i%2; //当前行
            int pre=1-cur; //上一行
            dp[cur][0]=dp[pre][0]+triangle[i][0]; //第一列只能从上面转移
            for(int j=1;j<i;j++){
                dp[cur][j]=min(dp[pre][j-1],dp[pre][j])+triangle[i][j];
            }
            dp[cur][i]=dp[pre][i-1]+triangle[i][i];//最后一列只能从左上转移
        }
        return *min_element(dp[(n-1)%2].begin(),dp[(n-1)%2].end());
    }
};

下降路径最小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n=matrix.size();
        vector<vector<int>> dp(n,vector<int>(n));
        copy(matrix[0].begin(),matrix[0].end(),dp[0].begin());
        for(int i=1;i<n;i++){
            for(int j=0;j<n;j++){
                int minn=dp[i-1][j]; //都能从正上方转移
                if(j>0){ //可以从左上方转移
                    minn=min(minn,dp[i-1][j-1]);
                }
                if(j<n-1){ //可以从右上方转移
                    minn=min(minn,dp[i-1][j+1]);
                }
                dp[i][j]=minn+matrix[i][j];
            }
        }
        return *min_element(dp[n-1].begin(),dp[n-1].end());
    }
};

矩阵中移动的最大次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int ans=0; bool flag=1;
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<int>> dp(n,vector<int>(m)); //dp[i][j]==1表示(i,j)位置可到达
        for(int i=0;i<n;i++) dp[i][0]=1; 
        for(int j=1;j<m;j++){
            if(!flag) return ans;
            flag=0;
            for(int i=0;i<n;i++){
                if(grid[i][j-1]<grid[i][j]&&dp[i][j-1]){
                    dp[i][j]=1;
                }
                if(i>0){
                    if(grid[i-1][j-1]<grid[i][j]&&dp[i-1][j-1]){
                        dp[i][j]=1;
                    }
                }
                if(i<n-1){
                    if(grid[i+1][j-1]<grid[i][j]&&dp[i+1][j-1]){
                        dp[i][j]=1;
                    }
                }
                if(dp[i][j]){
                    flag=1;
                    ans=j;
                }
            }
        }
        //ans+=1;
        return ans;
    }
};

网格中的最小路径代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dp(2,vector<int>(n));
        dp[0]=grid[0];
        for(int i=1;i<m;i++){
            int cur=i%2; //当前行
            int pre=1-cur; //上一行
            for(int j=0;j<n;j++){ //当前行每一列
                dp[cur][j]=INT_MAX;
                for(int k=0;k<n;k++){ //上一行每一列
                    dp[cur][j]=min(dp[cur][j],dp[pre][k]+moveCost[grid[i-1][k]][j]+grid[i][j]);
                }
            }
        }
        return *min_element(dp[(m-1)%2].begin(),dp[(m-1)%2].end());
    }
};

下降路径最小和 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        vector<vector<int>> dp(2,vector<int>(m));
        dp[0]=grid[0];
        for(int i=1;i<n;i++){ 
            int cur=i%2; //当前行
            int pre=1-cur; //上一行
            for(int j=0;j<m;j++){ //当前行每一列
                dp[cur][j]=INT_MAX;
                for(int k=0;k<m;k++){ //上一行每一列
                    if(j!=k){
                        dp[cur][j]=min(dp[cur][j],dp[pre][k]+grid[i][j]);
                    }
                }
            }
        }
        return *min_element(dp[(n-1)%2].begin(),dp[(n-1)%2].end());
    }
};

进阶

矩阵的最大非负积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        const int mod=1e9+7;
        int m=grid.size(),n=grid[0].size();
        vector<vector<long long>> maxgt(m,vector<long long>(n));
        vector<vector<long long>> minlt(m,vector<long long>(n));
        maxgt[0][0]=minlt[0][0]=grid[0][0];
        for(int j=1;j<n;j++){ //处理第一行
            maxgt[0][j]=minlt[0][j]=maxgt[0][j-1]*grid[0][j];
        }
        for(int i=1;i<m;i++){ //处理第一列
            maxgt[i][0]=minlt[i][0]=maxgt[i-1][0]*grid[i][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(grid[i][j]>=0){
                    maxgt[i][j]=max(maxgt[i-1][j],maxgt[i][j-1])*grid[i][j];
                    minlt[i][j]=min(minlt[i-1][j],minlt[i][j-1])*grid[i][j];
                }
                else{
                    maxgt[i][j]=min(minlt[i-1][j],minlt[i][j-1])*grid[i][j];
                    minlt[i][j]=max(maxgt[i-1][j],maxgt[i][j-1])*grid[i][j];
                }
            }
        }
        if(maxgt[m-1][n-1]<0) return -1;
        else{
            return maxgt[m-1][n-1]%mod;
        }
    }
};

最大得分的路径数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using PII = pair<int, int>;

class Solution {
private:
    static constexpr int mod = (int)1e9 + 7;

public:
    void update(vector<vector<PII>>& dp, int n, int x, int y, int u, int v) {
        if (u >= n || v >= n || dp[u][v].first == -1) {
            return;
        }
        if (dp[u][v].first > dp[x][y].first) {
            dp[x][y] = dp[u][v];
        }
        else if (dp[u][v].first == dp[x][y].first) {
            dp[x][y].second += dp[u][v].second;
            if (dp[x][y].second >= mod) {
                dp[x][y].second -= mod;
            }
        }
    }

    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size();
        vector<vector<PII>> dp(n, vector<PII>(n, {-1, 0}));
        dp[n - 1][n - 1] = {0, 1};
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (!(i == n - 1 && j == n - 1) && board[i][j] != 'X') {
                    update(dp, n, i, j, i + 1, j);
                    update(dp, n, i, j, i, j + 1);
                    update(dp, n, i, j, i + 1, j + 1);
                    if (dp[i][j].first != -1) {
                        dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');
                    }
                }
            }
        }
        return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};
    }
};

矩阵中和能被 K 整除的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*把路径和模 k 的结果当成一个扩展维度*/
class Solution {
public:
    int numberOfPaths(vector<vector<int>> &grid, int k) {
        const int mod = 1e9 + 7;
        int m = grid.size(), n = grid[0].size(), f[m + 1][n + 1][k];
        memset(f, 0, sizeof(f)); // f[i][j][v] 表示从左上走到 (i,j)，且路径和模 k 的结果为 v 时的路径数
        f[0][1][0] = 1;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                for (int v = 0; v < k; ++v)
                    f[i + 1][j + 1][(v + grid[i][j]) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % mod;
        return f[m][n][0];
    }
};
/*代码实现时，为了避免判断是否越界，可以把下标都加一。此时可以设初始值 f[0][1][0]=1（或者 f[1][0][0]=1）简化一点点代码。*/

地下城游戏

1

背包

0-1 背包

每个物品只能选一次

和为目标值的最长子序列的长度

1

完全背包

多重背包

分组背包

经典线性 DP

最长公共子序列（LCS）

一般定义f[i][j]表示对(s[:i],t[:j])的求解结果。

最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1)); 
        for(int i=1;i<=m;i++){
            char c1=text1[i-1];
            for(int j=1;j<=n;j++){
                char c2=text2[j-1];
                if(c1==c2){
                    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];
    }
};

两个字符串的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= m; i++) {
            char c1 = word1[i - 1];
            for (int j = 1; j <= n; j++) {
                char c2 = word2[j - 1];
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int lcs = dp[m][n];
        return m - lcs + n - lcs;
    }
};

两个字符串的最小ASCII删除和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= m; ++i) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            char c1 = s1[i - 1];
            for (int j = 1; j <= n; j++) {
                char c2 = s2[j - 1];
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }

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

编辑距离

1

最长递增子序列（LIS）