LeetCode - 刷题记录
个人LeetCode刷题之旅的记录，包含了个人的学习笔记和心得体会💕
开始使用

改题单选自灵神：分享丨【题单】动态规划（入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化） - 力扣（LeetCode）

一、入门 DP

1.0 题目清单

1. 爬楼梯

2. 打家劫舍

1.1 爬楼梯类

70. 爬楼梯

题目传送门：70. 爬楼梯 - 力扣（LeetCode）

简单递推直接秒了，最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1,0);
        dp[0] = 1; dp[1] = 1;
        for(int i=2;i<=n;++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

题目传送门：746. 使用最小花费爬楼梯 - 力扣（LeetCode）

同上，递推即可。

最后实现代码如下：

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

377. 组合总和 Ⅳ

题目传送门：377. 组合总和 Ⅳ - 力扣（LeetCode）

此题类似一个完全背包问题，这里需要注意一下内外循环顺序，先循环target再循环给定数组中的数。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned> dp(target+1,0);
        dp[0] = 1;
        int n = nums.size();
        for(int i=1; i<=target; ++i){
            for(int j=0; j<n; ++j){
                if (nums[j] > i) continue;
                dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
};

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

题目传送门：2466. 统计构造好字符串的方案数 - 力扣（LeetCode）

跟上面那道题目思路一样。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(1e5+2,0); dp[0] = 1;
        int MOD = 1e9+7;
        for(int i=1;i<=high;++i){
            if (i>=zero) dp[i] += dp[i-zero];
            if (i>=one)  dp[i] += dp[i-one];
            dp[i] %= MOD;
        }
        int ans = 0;
        for(int i=low; i<=high; ++i){
            ans = (ans + dp[i]) % MOD;
        }
        return ans;
    }
};

2266. 统计打字方案数

题目传送门：2266. 统计打字方案数 - 力扣（LeetCode）

仍然是爬楼梯类问题，但是并不是那种可以直接解决的，可以采用如下方式解决：

将相同字符分为一组，每组内只有一种字符。考虑以下动态规划（DP）方法：

  1. 对于字符不为7或9的情况，定义( f[i] )表示长度为( i )的只有一种字符的字符串对应的文字信息种类数。我们可以将末尾的1个、2个或3个字符单独视作一个字母，那么有转移方程：

f[i]=f[i−1]+f[i−2]+f[i−3]f[i] = f[i-1] + f[i-2] + f[i-3]

  1. 对于字符为7或9的情况，定义( g[i] )表示长度为( i )的只有一种字符的字符串对应的文字信息种类数，可以得到类似的转移方程：

g[i]=g[i−1]+g[i−2]+g[i−3]+g[i−4]g[i] = g[i-1] + g[i-2] + g[i-3] + g[i-4]

这样能算出每组字符串的文字信息种类数。

由于不同组之间互不影响，根据乘法原理，把不同组的文字信息种类数相乘，得到答案。

最后实现代码如下：

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 countTexts(string pressedKeys) {
        int MOD = 1e9 +7, n = pressedKeys.size();
        vector<long long> dp_3(100003,0),dp_4(100003,0); 
        dp_3[0] = 1; dp_3[1] = 1; dp_3[2] = 2; dp_3[3] = 4;
        dp_4[0] = 1; dp_4[1] = 1; dp_4[2] = 2; dp_4[3] = 4;
        for (int i=4;i<=n;++i) {
            dp_3[i] = dp_3[i-1] + dp_3[i-2] + dp_3[i-3];
            dp_4[i] = dp_4[i-1] + dp_4[i-2] + dp_4[i-3] + dp_4[i-4];
            dp_3[i] %= MOD;
            dp_4[i] %= MOD;
        }
        int cnt = 1;
        long long ans = 1;
        char ch = pressedKeys[0];
        for(int i=1;i<n;++i){
            if (pressedKeys[i]!=ch){
                if (ch == '7'||ch == '9') ans = (dp_4[cnt] * ans) % MOD;
                else ans = (dp_3[cnt] * ans) % MOD;
                cnt = 1;
                ch = pressedKeys[i];
            } else {
                cnt++;
            }
        }
        int tmp;
        if(ch == '7'||ch == '9') tmp = dp_4[cnt];
        else tmp = dp_3[cnt];
        return ((ans*tmp)%MOD);
    }
};

1.2 打家劫舍

198. 打家劫舍

题目传送门：198. 打家劫舍 - 力扣（LeetCode）

定义动态规划数组dp[i]表示偷到第i个房子，所能盗取的最大金额。

那么不难写出状态转移方程：

1
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);

最后确定一下初始状态dp[0] = 0,dp[1] = nums[0],完成解答。

最后实现代码如下：

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

740. 删除并获得点数

题目传送门：740. 删除并获得点数

观察数据范围后不难发现就是上面打家劫舍这种类型的题目，排序后，动态规划同上一题目。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        vector<int>nums_all(10004, 0), dp(10004, 0);
        sort(nums.begin(), nums.end());
        int prev = nums[0], cnt = 0;
        for(int i=0;i<n;++i){
            if (nums[i]==prev) cnt++;
            else {
                nums_all[prev] = cnt * prev;
                cnt = 1; prev = nums[i]; 
            }
        }
        nums_all[prev] = prev * cnt;
        dp[1] = nums_all[1];
        for(int i=2;i<=nums[n-1];++i){
            dp[i] = max(dp[i-1], dp[i-2]+nums_all[i]);
        }
        return dp[nums[n-1]];
    }
};

2320. 统计放置房子的方式数

题目传送门：2320. 统计放置房子的方式数 - 力扣（LeetCode）

观察每个位置的放置状态一共有4种情况：

  1. 上无下无
  2. 上有下无
  3. 上无下有
  4. 上有下有
    因此可以设计一个dp[n][4]动态规划数组，对于当前每一种状态，都可以从上一个位置其他状态推导而来，最后的答案就是最后一个位置的所有4种状态之和。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countHousePlacements(int n) {
        int MOD = 1e9 + 7;
        vector<vector<int>> dp(10002,vector<int>(4,0));
        dp[1][0] = 1; dp[1][1] = 1; dp[1][2] = 1; dp[1][3] = 1;
        for(int i=2;i<=n;++i){
            dp[i][1] = (dp[i-1][0] + dp[i-1][2])%MOD;
            dp[i][2] = (dp[i-1][0] + dp[i-1][1])%MOD;
            dp[i][3] = dp[i-1][0];
            dp[i][0] = ((dp[i-1][0]+dp[i-1][1])%MOD + (dp[i-1][2]+dp[i-1][3])%MOD)%MOD;
        }
        return ((dp[n][0]+dp[n][1])%MOD + (dp[n][2]+dp[n][3])%MOD)%MOD;
    }
};

213. 打家劫舍 II

题目传送门：213. 打家劫舍 II - 力扣（LeetCode）

此题就是之前的打家劫舍但是将顺序的结构改成了环形的结构。为了防止同时选到第一个和最后一个，可以做两遍DP。

注意：

最后实现代码如下：

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 rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp1(n+2,0), dp2(n+2,0);
        // 特殊判断（只有一个元素）
        if (n == 1) return nums[0];
        // 不选第一个
        dp1[1] = 0;
        for(int i=2;i<=n;++i){
            dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i-1]);
        }
        // 不选最后一个
        dp2[1] = nums[0];
        for(int i=2;i<n;++i){
            dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i-1]);
        }
        return max(dp1[n], dp2[n-1]);

    }
};

1.3 最大子数组和（最大子段和）

53. 最大子数组和

题目传送门：53. 最大子数组和 - 力扣（LeetCode）

不同于之前的DP，这里定义的DP数组dp[i]含义是，以第i个数结尾的连续子数组最大和（因为条件中包含连续这一要求，因此只有这样才能描述状态转移方程）

最后实现代码如下：

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

2606. 找到最大开销的子字符串

题目传送门：2606. 找到最大开销的子字符串 - 力扣（LeetCode）

思路同上

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        int n = s.size();
        vector<int> dp(n+2,0);
        unordered_map<char,int> mp;
        int m = chars.size();
        for(int i=0; i<26; ++i) mp['a'+i] = i+1;
        for(int i=0; i<m; ++i) mp[chars[i]] = vals[i];
        for(int i=1;i<=n;++i) {
            int val = mp[s[i-1]];
            dp[i] = max(dp[i-1]+val, val);
        }
        int ans = dp[0];
        for(int i=1;i<=n;++i) ans = max(ans, dp[i]);
        return ans;
    }
};

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

题目传送门：1749. 任意子数组和的绝对值的最大值 - 力扣（LeetCode）

思路上和之前一样，

最后实现代码如下：

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

这道题这样做可能还麻烦了一些，还可以利用前缀和的思想进行简化。具体而言就是找到这个数组中前缀和最大和前缀和最小，相减就可以得出想要的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int maxx = 0, minn = 0;
        int nw=0;
        for(int num : nums){
            nw += num;
            maxx = max(maxx, nw);
            minn = min(minn, nw);
        }
        return maxx - minn;
    }
};

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

题目传送门：1191. K 次串联后最大子数组之和 - 力扣（LeetCode）

此题定义的DP数组（实际未定义，使用一个变量优化掉了）同之前一样，也是表现的是以当前数结尾的最大子数组和。

这里需要注意的是题目中的k其实是吓人的，我们仔细分析一下便可得知:

  • 当k为1时，同最大子数组和
  • 当k为2时，由于存在特殊情况（选第一个数组后缀+第二个数组的前缀）将数组拼接在一起，同理可以转变为最大子数组和
  • 当k大于2时，相比上一种情况，要多考虑，如果出现横跨数组的情况的话，相当于中间数组的和加上单个数组的最大前缀和与最大后缀和。

综上分三类讨论即可。实际上没有将数组扩展k倍。

最后实现代码如下：

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 kConcatenationMaxSum(vector<int>& arr, int k) {
        int n = arr.size();
        int MOD = 1e9 + 7; 
        long long maxx = 0,minn = 0,sum_arr = 0;// 前缀和
        // 前缀和预处理
        for(int i=0;i<n;++i){
            sum_arr += arr[i];
            maxx = max(maxx, sum_arr);
            minn = min(minn, sum_arr);
        }
        if (k!=1) arr.insert(arr.end(),arr.begin(),arr.end());
        int m = arr.size();
        long long tmp = 0,ans=0;
        for(int i=0;i<m;++i){
            tmp = max(tmp,(long long)(0)) + arr[i];
            ans = max(ans, tmp);
        }
        if (k<=2) return ans%MOD;
        else return max(ans, (k-2)*sum_arr + maxx + sum_arr-minn)%MOD;
    }
};

918. 环形子数组的最大和

题目传送门：918. 环形子数组的最大和 - 力扣（LeetCode）

同样还是分类讨论的思想。

对于非环形数组的情况，其解决方法类似于寻找最大子数组和，这里不再详述。而对于环形数组，可以将问题转化为寻找最大的前缀和与后缀和，这两部分不能有交集。通过计算每个位置的最大前后缀和，可以解决环形问题。因此，整体问题可视为求解“最大子数组和”与“最大前后缀和”的较大者。最终，比较这两个结果，返回较大的值即可。

最后实现代码如下：

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 maxSubarraySumCircular(vector<int>& nums) {
        // 数组内最大值
        int ans1=nums[0], tmp=0;
        for(auto num : nums){
            tmp = max(num, num + tmp);
            ans1 = max(tmp,ans1);
        } 
        // 维护前后缀最大值
        int n = nums.size();
        vector<int> pre(n+1,0),pos(n+1,0);
        int pre_tmp = 0, pos_tmp = 0;
        for(int i=1;i<=n;++i){
            pre_tmp += nums[i-1];
            if(i>1) pre[i] = max(pre[i-1], pre_tmp);
            else pre[i] = pre_tmp;
            pos_tmp += nums[n-i];
            if(i>1) pos[i] = max(pos[i-1], pos_tmp);
            else pos[i] = pos_tmp;
        }
        int ans2 = pre[1]+pos[n-1];
        for(int i=1;i<n;++i){
            ans2 = max(ans2,pre[i]+pos[n-i]);
        }
        return max(ans1, ans2);
    }
};

2321. 拼接数组的最大分数

题目传送门：2321. 拼接数组的最大分数 - 力扣（LeetCode）

我们将两个数组作差得到两个差值数组diff1和diff2，仔细观察后可以将此题转化为最大子数组和这个问题，

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),sum1=0,sum2=0;
        int max2=0,max1=0,tmp1=0,tmp2=0;
        for(int i=0;i<n;++i) {
            sum1 += nums1[i]; sum2 += nums2[i];
            tmp1 = max(tmp1, 0) + nums1[i] - nums2[i];
            tmp2 = max(tmp2, 0) + nums2[i] - nums1[i];
            max1 = max(max1, tmp1); max2 = max(max2, tmp2);
        }
        return max(sum1 + max2, sum2 + max1);
    }
};

152. 乘积最大子数组

题目传送门：152. 乘积最大子数组 - 力扣（LeetCode）

该题作为最大子数组和的一个扩展，还是非常有意思，多维护一个最小值就可以。

注意：最大值同理也可以状态转移到最小值，最小值同理也可以状态转移到最大值 (比如当前位置是一个负数，就可能发生上述转化)

这里面有一个很“有趣”的测试用例:

1
[0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]

这个用例很有趣，最大会有 10^19 要存储，加上符号位是65位，刚好不够 long long 来存。而double虽然也是64位，但它的数据结构有所不同，采用 1符号+11指数+52 尾数的方式，最多可以存到 2^1024 的大数。虽然在 52位二进制数以上的精度不能保证，但这题由题目保证最多只用到32位，再多的只是为了满足不溢出。 所以，我们将临时变量由 int 改为 double，即可通过此用例。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        double ans=nums[0], max_now=nums[0],min_now=nums[0];
        int n = nums.size();
        for(int i=1;i<n;++i){
            double max_tmp = max_now, min_tmp = min_now;
            max_now = max(max_now*nums[i], max((double)nums[i],min_tmp*nums[i]));
            min_now = min(min_now*nums[i], min((double)nums[i],max_tmp*nums[i]));
            ans = max(ans,max_now);
        }
        return int(ans);
    }
};

二、网格图 DP

2.0 题目清单

1. 基础

2.1 基础

LCR 166. 珠宝的最高价值

题目传送门：LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

网格DP求最大值题，网格图DP基础板子题，从左侧和上侧进行状态转移即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n = frame.size(), m = frame[0].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){
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + frame[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};

62. 不同路径

题目传送门：62. 不同路径 - 力扣（LeetCode）

网格DP方案数题，同上，网格图DP基础板子题，从左侧和上侧进行状态转移即可。

注意一下初始化即可。

最后实现代码如下：

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

63. 不同路径 II

题目传送门：63. 不同路径 II - 力扣（LeetCode）

网格DP方案数题，在上一道题的基础上增加了障碍物的设定，只需要在每次循环的时候判定当前是不是障碍物即可，如果是就不更新。

最后实现代码如下：

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

64. 最小路径和

题目传送门：64. 最小路径和 - 力扣（LeetCode）

网格DP求最小值题，上面已经遇到了方案数量和求最大的设定，此题为一个求最小设定。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n+1,vector<int>(m+1, INT_MAX/2));
        dp[0][1] = 0; dp[1][0] = 0;
        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-1][j-1];
            }
        }
        return dp[n][m];
    }
};

120. 三角形最小路径和

题目传送门：120. 三角形最小路径和 - 力扣（LeetCode）

网格DP求最小值题，上一道题的简单改版，从矩形变成了三角形，最后判断一下最后一行最小的值即可。

备注：顺便可以看一下min_element的用法

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, (INT_MAX/2)));
        dp[1][1] = triangle[0][0];
        for(int i=2;i<=n;++i){
            for(int j=1;j<=i;++j){
                dp[i][j] = triangle[i-1][j-1] + min(dp[i-1][j-1] , dp[i-1][j]);
            }
        }
        return *min_element(dp[n].begin(), dp[n].end());
    }
};

931. 下降路径最小和

题目传送门：931. 下降路径最小和 - 力扣（LeetCode）

网格DP求最小值题，同上，从上一行相邻三个转移，使用上一行三个值中的最小值加上当前位置值即可。

最后实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX/2));
        for(int i=1;i<=n;++i) dp[0][i] = 0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i-1][j+1])) + matrix[i-1][j-1];
            }
        }
        return *min_element(dp[n].begin()+1, dp[n].begin()+1+n);
    }
};

2684. 矩阵中移动的最大次数

题目传送门：2684. 矩阵中移动的最大次数 - 力扣（LeetCode）

网格DP求最大值题，同上，只不过需要在更新的过程中时刻维护一个全局步数的最大值即可。

最后实现代码如下：

1

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。