笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

代码随想录leetcode200题之动态规划算法

作者：笔触狂放9 | 2024-08-23 07:45:14

踩

1 介绍

本博客用来记录代码随想录leetcode200题之动态规划算法相关题目。

2 训练

题目1：509. 斐波那契数

C++代码如下，

class Solution {
public:
    int fib(int n) {
        if (n <= 1) { //特判
            return n;
        }
        int a = 0, b = 1;
        for (int i = 2; i <= n; ++i) {
            int t = a + b;
            a = b;
            b = t;
        }
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python3代码如下，

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: #特判
            return n 
        a, b = 0, 1
        for i in range(2,n+1):
            a, b = b, a + b
        return b
1
2
3
4
5
6
7
8

题目2：70. 爬楼梯

C++代码如下，

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) { //特判
            return n;
        }
        int a = 1, b = 2;
        for (int i = 3; i <= n; ++i) {
            int t = a + b;
            a = b;
            b = t;
        }
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python3代码如下，

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: #特判
            return n
        a, b = 1, 2
        for i in range(3,n+1):
            a, b = b, a + b
        return b
1
2
3
4
5
6
7
8

题目3：746. 使用最小花费爬楼梯

C++代码如下，

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n+1, 0);
        //状态定义
        //dp[i]:跑到第i层阶梯所需的最小花费
        //状态转移
        //dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        //状态初始化
        //dp[0] = 0, dp[1] = 0
        for (int i = 2; i < n+1; ++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

python3代码如下，

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n+1)
        #状态定义
        #dp[i]:爬到第i个阶梯的最小花费
        #状态转移
        #dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        #状态初始化
        #dp[0] = 0, dp[1] = 0
        for i in range(2, n+1):
            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

题目4：62. 不同路径

C++代码如下，

数学解法如下，

class Solution {
public:
    int uniquePaths(int m, int n) {
        m -= 1;
        n -= 1;
        //计算C[n+m][n]
        long long ans = 1;
        for (int i = m+1, j = 0; j < n; ++j, ++i) {
            ans = ans * i / (j + 1);
        }
        return ans;
    }
};
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(n, vector<int>(m, 0));
        //状态定义
        //dp[i][j]:从(0,0)走到(i,j)的走法
        //状态转移
        //dp[i][j] = dp[i-1][j] + dp[i][j-1]
        //状态初始化
        //dp[i][0] = 1
        //dp[0][j] = 1
        for (int i = 0; i < n; ++i) dp[i][0] = 1;
        for (int j = 0; j < m; ++j) dp[0][j] = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
            }
        }
        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

python3代码如下，

数学解法，

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        m -= 1
        n -= 1
        #计算组合数C[n+m][m]
        i = n+1
        j = 1
        res = 1
        while j <= m:
            res = res * i / j
            j += 1
            i += 1
        return int(res)
1
2
3
4
5
6
7
8
9
10
11
12
13

#C++中可能会超过整型数值范围
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        m -= 1
        n -= 1
        C = [[0] * 110 for _ in range(110)]
        for i in range(110):
            for j in range(i+1):
                if j == 0:
                    C[i][j] = 1
                else:
                    C[i][j] = C[i-1][j] + C[i-1][j-1]
        return C[m+n][m]
1
2
3
4
5
6
7
8
9
10
11
12
13

#C++中可能会超过整型数值范围
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        m -= 1
        n -= 1
        #求C[n+m][m]
        fa = 1
        fb = 1
        for i in range(1,n+1):
            fa *= m + n - i + 1
            fb *= i 
        res = fa // fb
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13

动态规划解法

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = 1
        for i in range(1,n):
            dp[i][0] = dp[i-1][0]
        for j in range(1,m):
            dp[0][j] = dp[0][j-1]
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]
1
2
3
4
5
6
7
8
9
10
11
12

题目5：63. 不同路径 II

C++代码如下，

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

python3代码如下，

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n = len(obstacleGrid)
        m = len(obstacleGrid[0])
        dp = [[0] * m for _ in range(n)]
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(1,n):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i-1][0]
        for j in range(1,m):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j-1]
        for i in range(1,n):
            for j in range(1,m):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目6：343. 整数拆分

C++代码如下，

class Solution {
public:
    int integerBreak(int n) {
        int res = 1;
        for (int k = 2; k <= n; ++k) {
            //将n拆分成k个数
            int a = n / k;
            vector<int> nums(k, a);
            int t = n - a * k;
            for (int i = 0; i < t; ++i) nums[i] += 1;
            int ans = 1;
            for (auto x : nums) ans *= x;
            res = max(res, ans);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

python3代码如下，

class Solution:
    def integerBreak(self, n: int) -> int:
        res = 1 #答案的理论最小值
        for k in range(2,n):
            #将n拆分成k个数
            a = n // k
            nums = [a] * k
            t = n - a * k
            for i in range(t):
                nums[i] += 1
            ans = 1
            for x in nums:
                ans *= x 
            res = max(res, ans)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目7：96. 不同的二叉搜索树

C++代码如下，

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

python3代码如下，

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1) 
        dp[0] = 1
        for i in range(n+1):
            for j in range(1,i+1):
                dp[i] += dp[j-1] * dp[i-j]
        return dp[n] 
1
2
3
4
5
6
7
8

题目8：46. 携带研究材料（第六期模拟笔试）

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010, M = 5010;
int v[N];
int w[N];
int m;
int n;
int dp[M];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = M; j - v[i] >= 0; --j) {
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout << dp[m] << endl;
    
    return 0;
}
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

python3代码如下，

import sys 

data = sys.stdin.read()
lines = data.splitlines()
n, m = map(int, lines[0].split())
v = list(map(int, lines[1].split()))
w = list(map(int, lines[2].split()))

dp = [0] * (m + 10)
for i in range(n):
    for j in range(m,v[i]-1,-1):
        dp[j] = max(dp[j], dp[j-v[i]] + w[i])
print(dp[m])
1
2
3
4
5
6
7
8
9
10
11
12
13

题目9：416. 分割等和子集

C++代码如下，

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        if (totalSum % 2 != 0) return false;
        int targetSum = totalSum / 2;
        vector<int> dp(targetSum + 10, 0);
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = targetSum; j >= nums[i]; --j) {
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[targetSum] == targetSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python3代码如下，

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        totalSum = sum(nums)
        if totalSum % 2 != 0:
            return False
        targetSum = totalSum // 2
        #从nums中能否找到一些数，使得它们之和等于targetSum
        #套用01背包模型
        dp = [0] * (targetSum + 10)
        for i in range(len(nums)):
            for j in range(targetSum, nums[i]-1, -1):
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
        return dp[targetSum] == targetSum
1
2
3
4
5
6
7
8
9
10
11
12
13

题目10：1049. 最后一块石头的重量 II

C++代码如下，

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int totalSum = accumulate(stones.begin(), stones.end(), 0);
        int m = totalSum / 2;
        int n = stones.size();
        vector<int> dp(m + 1, 0);
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= stones[i]; --j) {
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        int a = dp[m];
        int b = totalSum - a;
        return abs(a-b);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

python3代码如下，

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        #装换成01背包模型
        totalSum = sum(stones)
        m = totalSum // 2
        n = len(stones)
        dp = [0] * (m + 1)
        for i in range(n):
            for j in range(m,stones[i]-1,-1):
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        a = dp[m]
        b = totalSum - a
        return abs(a - b)
1
2
3
4
5
6
7
8
9
10
11
12
13

题目11：494. 目标和

解题思路：要加上的数记为left，要减去的数计为right，由题意，left + right = sum(a)，而left - right = target，化简可得，left = (sum(a) + target) / 2。特别注意，由于left是整数，因此如果sum(a) + target不能被2整除的话，那么无解。此外target > sum(a)时，也无解。接下来就是背包问题的变体，求填满体积为left的背包的方案数。

C++代码如下，

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if ((target + sum) % 2 != 0 || target > sum) return 0; //特判
        int m = (target + sum) / 2;
        if (m < 0) return 0; //特判
        int n = nums.size();
        vector<int> f(m+1, 0);
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= nums[i]; --j) {
                f[j] += f[j-nums[i]];
            }
        }
        return f[m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

python3代码如下，

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        #01背包求最大价值->01背包问题求方案数
        totalSum = sum(nums)
        if target > totalSum:
            return 0
        if (target + totalSum) % 2 != 0:
            return 0 
        m = (target + totalSum) // 2
        if m < 0:
            return 0
        n = len(nums)
        dp = [0] * (m + 1)
        #状态定义
        #dp[j]:填满容积为j的背包，有多少种方案数
        #状态转移
        #dp[j] += d[j-nums[i]]
        #状态初始化
        #dp[0] = 1
        dp[0] = 1
        for i in range(n):
            for j in range(m, nums[i]-1, -1):
                dp[j] += dp[j-nums[i]]
        return dp[m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目12：474. 一和零

解题思路：存放1的背包的最大容积为n，存放0的背包的最大容积为m，每件物品的价值为1。01背包问题求最大价值变体。

C++代码如下：

//二维状态
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));
        f[0][0] = 0;
        for (auto str : strs) {
            int cnt0 = count(str.begin(), str.end(), '0');
            int cnt1 = count(str.begin(), str.end(), '1');
            for (int i = n; i >= cnt1; --i) {
                for (int j = m; j >= cnt0; --j) {
                    f[i][j] = max(f[i][j], f[i-cnt1][j-cnt0] + 1);
                }
            }
        }
        return f[n][m];
    }
};

//三维状态  注意遍历顺序
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int ssize = strs.size();
        vector<vector<vector<int>>> f(ssize+1, vector<vector<int>>(n+1, vector<int>(m+1, 0)));
        f[0][0][0] = 0;
        for (int k = 1; k <= ssize; ++k) {
            int cnt0 = count(strs[k-1].begin(), strs[k-1].end(), '0');
            int cnt1 = count(strs[k-1].begin(), strs[k-1].end(), '1');
            for (int i = 0; i <= n; ++i) {
                for (int j = 0; j <= m; ++j) {
                    f[k][i][j] = f[k-1][i][j];
                    if (i >= cnt1 && j >= cnt0) {
                        f[k][i][j] = max(f[k][i][j], f[k-1][i-cnt1][j-cnt0] + 1);
                    }
                }
            }
        } 
        return f[ssize][n][m];
    }
};
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

python3代码如下，

#二维状态表示
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        idxsize = len(strs)
        strs.insert(0, "")
        f = [[0] * (m+1) for _ in range(n+1)] #(n+1)*(m+1)
        #n个1,m个0
        #背包求最大价值
        f[0][0] = 0
        for k in range(1,idxsize+1):
            cnt0 = strs[k].count('0')
            cnt1 = strs[k].count('1')
            for i in range(n,cnt1-1,-1):
                for j in range(m,cnt0-1,-1):
                    f[i][j] = max(f[i][j], f[i][j]) #不选择第k个物品
                    f[i][j] = max(f[i][j], f[i-cnt1][j-cnt0] + 1) #选择第k个物品
        return f[n][m]
#三维状态表示
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        idxsize = len(strs)
        strs.insert(0, "")
        f = [[[0] * (m+1) for _ in range(n+1)] for _ in range(idxsize+1)] #(idxsize+1)*(n+1)*(m+1)
        #n个1,m个0
        #背包求最大价值
        f[0][0][0] = 0
        for k in range(1,idxsize+1):
            cnt0 = strs[k].count('0')
            cnt1 = strs[k].count('1')
            for i in range(0,n+1):
                for j in range(0,m+1):
                    f[k][i][j] = f[k-1][i][j] #不选择第k个物品
                    if i >= cnt1 and j >= cnt0:
                        f[k][i][j] = max(f[k][i][j], f[k-1][i-cnt1][j-cnt0] + 1) #选择第k个物品
        return f[idxsize][n][m]
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

题目13：52. 携带研究材料（第七期模拟笔试）

解题思路：完全背包问题求最大价值。遍历背包容积时，从小到大遍历。详细推导过程请参见acwing算法基础之动态规划–背包问题

C++代码如下，

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;
int v[N];
int w[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i];
    }
    
    vector<int> f(m+1,0);
    for (int i = 0; i < n; ++i) {
        for (int j = v[i]; j <= m; ++j) {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    
    return 0;
}
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

python3代码如下，

#一维状态
import sys

data = sys.stdin.read()
data = data.splitlines()
n, m = 0, 0
v = []
w = []

for i, row in enumerate(data):
    if i == 0:
        n, m = map(int, row.split())
    else:
        x, y = map(int, row.split())
        v.append(x)
        w.append(y)

#完全背包问题
f = [0] * (m + 1)
for i in range(n):
    for j in range(v[i],m+1):
        f[j] = max(f[j], f[j-v[i]] + w[i])
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目14：518. 零钱兑换 II

解题思路：完全背包模型求方案数。注意遍历顺序。

C++代码如下，

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

python3代码如下，

class Solution:
    def change(self, m: int, coins: List[int]) -> int:
        #完全背包求方案数
        n = len(coins)
        f = [0] * (m + 1)
        f[0] = 1
        for i in range(n):
            for j in range(coins[i],m+1):
                f[j] += f[j-coins[i]]
        return f[m]
1
2
3
4
5
6
7
8
9
10

题目15：377. 组合总和 Ⅳ

解题思路：本题也是完全背包求方案数。而本题是考虑顺序，也就是说，1 3和3 1是不同的方案。这时，记住Carl哥的定理：求组合数，先遍历物品，后遍历容积；求排列数，先遍历容积，后遍历物品。

C++代码如下，

class Solution {
public:
    int combinationSum4(vector<int>& nums, int m) {
        int n = nums.size();
        vector<int> f(m + 1, 0);
        f[0] = 1;
        //完全背包求方案数，考虑排列
        for (int j = 0; j <= m; ++j) {
            for (int i = 0; i < n; ++i) {
                if (j >= nums[i] && f[j] <= INT_MAX - f[j-nums[i]]) {
                    //f[j] <= INT_MAX - f[j-nums[i]]是为了不超出整型最大值，因为题目中说了，答案在整型范围内
                    f[j] += f[j-nums[i]];
                }
            }
        }
        return f[m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

python3代码如下，

class Solution:
    def combinationSum4(self, nums: List[int], m: int) -> int:
        #完全背包求方案数 组合问题
        #考点：如何将其转换为排列问题
        n = len(nums)
        f = [0] * (m + 1)
        f[0] = 1
        for j in range(0,m+1):
            for i in range(n):
                if j >= nums[i]:
                    f[j] += f[j-nums[i]]
        return f[m]
1
2
3
4
5
6
7
8
9
10
11
12

题目16：57. 爬楼梯（第八期模拟笔试）

解题思路：完全背包问题求方案数，注意考虑顺序，那么需要先遍历容积，后遍历物品。

C++代码如下，

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    swap(n, m);
    //m表示背包容积，n表示物品数目
    vector<int> f(m+1,0);
    f[0] = 1;
    for (int j = 0; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (j >= i) {
                f[j] += f[j-i];
            }
        }
    }
    cout << f[m] << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

python3代码如下，

import sys 

#完全背包模型求方案数，考虑顺序
data = sys.stdin.read()
data = data.splitlines()
for row in data:
    m, n = map(int, row.split())
f = [0] * (m + 1)
f[0] = 1
for j in range(m+1):
    for i in range(1,n+1):
        if j >= i:
            f[j] += f[j-i]
print(f[m])
1
2
3
4
5
6
7
8
9
10
11
12
13
14

题目17：322. 零钱兑换

解题思路：动态规划。

C++代码如下：

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

python3代码如下，

class Solution:
    def coinChange(self, coins: List[int], m: int) -> int:
        #状态表示:
        #f[j]:表示兑换成i的最少的硬币数目
        #状态转移:
        #f[j] = min(f[j], f[j-coins[i]] + 1) 0 <= i < len(coins)
        #状态初始化
        #f初始化为最大值,f[0]=0
        f = [1e20] * (m + 1)
        f[0] = 0
        for j in range(m+1):
            for i in range(len(coins)):
                if j >= coins[i]:
                    f[j] = min(f[j], f[j-coins[i]] + 1)
        if f[m] == 1e20:
            f[m] = -1
        return f[m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目18：279. 完全平方数

解题思路：动态规划。

C++代码如下：

class Solution {
public:
    int numSquares(int n) {
        vector<int> f;
        for (int i = 0; i <= n; ++i) {
            f.emplace_back(i);
        }
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j * j > i) break;
                f[i] = min(f[i], f[i-j*j]+1);
            }
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

python3代码如下：

class Solution:
    def numSquares(self, n: int) -> int:
        #f[i]表示i的最小数量
        #f[i] = min(f[i], f[i-j*j]+1)
        f = [i for i in range(n+1)]
        f[0] = 0
        f[1] = 1
        for i in range(2,n+1):
            for j in range(1,i):
                if j * j > i:
                    break
                f[i] = min(f[i], f[i-j*j]+1)
        return f[n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

题目19：139. 单词拆分

解题思路：python的话，可以使用记忆化搜索。C++的话，动态规划。

C++代码如下，

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        s = '#' + s;
        //f[i]表示s[1:i]的子区间是否能够匹配上
        //s.substr(i-word.size()+1,word.size()) == word, f[i] = f[i] || f[i-word.size()]
        //f[0] = true
        //f[n-1]
        int n = s.size();
        vector<bool> f(n, false);
        f[0] = true;
        for (int i = 1; i < n; ++i) {
            for (auto word : wordDict) {
                int m = word.size();
                if (i-m+1 >= 0 && s.substr(i-m+1,m) == word) {
                    f[i] = f[i] || f[i-m];
                }
            }
        }
        return f[n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

python3代码如下，

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        @lru_cache
        def dfs(s: str, wordDict: tuple, i: int) -> bool:
            if i == len(s):
                return True 
            for word in wordDict:
                m = len(word)
                if i+m <= len(s) and s[i:i+m] == word:
                    if dfs(s, wordDict, i+m):
                        return True 
            return False 
        return dfs(s, tuple(wordDict), 0)
1
2
3
4
5
6
7
8
9
10
11
12
13

题目20：56. 携带矿石资源（第八期模拟笔试）

解题思路：多重背包问题，也就是每个物品有一个最大的选择个数，这时候可以把这个选择次数，拆分成2的倍数及一个剩余数的组合，例如12 = 1 + 2 + 4 + 5。然后就是一个01背包问题喽。

C++代码如下，

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;
int m, n;
int v1[N], w1[N], s1[N];
int v[N*14], w[N*14];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v1[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> w1[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> s1[i];
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int a = v1[i];
        int b = w1[i];
        int c = s1[i];
        int k = 1;
        while (c >= k) {
            v[cnt] = k * a;
            w[cnt] = k * b;
            cnt += 1;
            c -= k;
            k <<= 1;
        }
        if (c > 0) {
            v[cnt] = c * a;
            w[cnt] = c * b;
            cnt += 1;
        }
    }
    
    vector<int> f(m+1,0);
    for (int i = 0; i < cnt; ++i) {
        for (int j = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j-v[i]]+w[i]);
        }
    }
    cout << f[m] << endl;
    
    return 0;
}
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
42
43
44
45
46
47
48
49
50

python3代码如下，

import sys 

data = sys.stdin.read()
data = data.splitlines()
m, n = map(int, data[0].split())
v1 = data[1].split()
v1 = [int(x) for x in v1]
w1 = data[2].split()
w1 = [int(x) for x in w1] 
s1 = data[3].split()
s1 = [int(x) for x in s1]
# print(f"m={m},n={n}")
# print(f"v1={v1},w1={w1},s1={s1}")
v = []
w = []
for i in range(n):
    a = v1[i]
    b = w1[i]
    c = s1[i]
    k = 1 
    while c >= k:
        v.append(k * a) 
        w.append(k * b) 
        c -= k 
        k <<= 1 
    if c > 0:
        v.append(c * a) 
        w.append(c * b) 
f = [0] * (m + 1)
for i in range(len(v)):
    for j in range(m, v[i]-1, -1):
        f[j] = max(f[j], f[j-v[i]]+w[i])
# print(f"f={f}")
print(f[m])
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

题目21：198. 打家劫舍

解题思路：动态规划。f[i][0]：从nums[0~i]中选择，且不选择nums[i]所能获得的最大值。f[i][1]：从nums[0~i]中选择，且选择nums[i]所能获得的最大值。

C++代码如下，

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

python3代码如下，

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[0] * 2 for _ in range(n)]
        f[0] = [0, nums[0]]
        for i in range(1,n):
            f[i][0] = max([f[i][0], f[i-1][0], f[i-1][1]])
            f[i][1] = max([f[i][1], f[i-1][0]+nums[i]])
        return max(f[n-1][0], f[n-1][1])
1
2
3
4
5
6
7
8
9

题目22：213. 打家劫舍 II

解题思路：分类讨论，不选nums[0]，动态规划一次；不选nums[n-1]，动态规划一次。

C++代码如下，

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) { //特判
            return nums[0];
        }
        vector<vector<int>> f(n, vector<int>(2, 0));
        //不选nums[0]
        f[1][0] = 0;
        f[1][1] = nums[1];
        for (int i = 2; i < n; ++i) {
            f[i][0] = max(f[i][0], f[i-1][0]);
            f[i][0] = max(f[i][0], f[i-1][1]);
            f[i][1] = max(f[i][1], f[i-1][0] + nums[i]); 
        }
        int ans1 = max(f[n-1][0], f[n-1][1]);
        //不选nums[n-1]
        f = vector<vector<int>>(n, vector<int>(2, 0));
        f[0][0] = 0;
        f[0][1] = nums[0];
        for (int i = 1; i < n-1; ++i) {
            f[i][0] = max(f[i][0], f[i-1][0]);
            f[i][0] = max(f[i][0], f[i-1][1]);
            f[i][1] = max(f[i][1], f[i-1][0] + nums[i]);             
        }
        int ans2 = max(f[n-2][0], f[n-2][1]);
        return max(ans1, ans2);
    }
};
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

python3代码如下，

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        #不选第0个
        f = [[0, 0] for _ in range(n)]
        f[1][0] = 0
        f[1][1] = nums[1]
        for i in range(2,n):
            f[i][0] = max([f[i][0], f[i-1][0], f[i-1][1]])
            f[i][1] = max([f[i][1], f[i-1][0] + nums[i]])
        ans1 = max(f[n-1][0], f[n-1][1])
        #不选第n-1个
        f = [[0,0] for _ in range(n)]
        f[0][0] = 0
        f[0][1] = nums[0]
        for i in range(1,n-1):
            f[i][0] = max([f[i][0], f[i-1][0], f[i-1][1]])
            f[i][1] = max([f[i][1], f[i-1][0] + nums[i]])
        ans2 = max(f[n-2][0], f[n-2][1])
        return max(ans1, ans2) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目23：337. 打家劫舍 III

解题思路：python3可以使用记忆化搜索来求解。C++也是记忆化搜索来求解。

C++代码如下，

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        unordered_map<TreeNode*, int> f1; //父结点已经被选择
        unordered_map<TreeNode*, int> f2; //父结点没有被选择
        function<int(TreeNode*,bool)> dfs =[&] (TreeNode* node, bool flag) -> int {
            //flag=true表示node的父结点已经被选择，那么不可以选择它
            //flag=false表示node的父结点没有被选择
            if (node == nullptr) {
                return 0; //特判
            }
            if (flag) {
                //不选择node
                if (f1.count(node) == 0) {
                    f1[node] = dfs(node->left,false);
                    f1[node] += dfs(node->right,false);
                    return f1[node];
                } else {
                    return f1[node];
                }
            } else {
                //不选择node
                if (f2.count(node) == 0) {
                    int res1 = dfs(node->left,false);
                    res1 += dfs(node->right,false);
                    //选择node
                    int res2 = node->val;
                    res2 += dfs(node->left,true);
                    res2 += dfs(node->right,true);
                    f2[node] =  max(res1, res2);
                    return f2[node];
                } else {
                    return f2[node];
                }
            }
        };
        return max(dfs(root,false), dfs(root,true));
    }
};
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
42
43
44
45
46
47
48
49
50

python3代码如下，

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        @lru_cache
        def dfs(node: Optional[TreeNode], flag: bool) -> int:
            #以node为根结点的子树所能获得的最大值
            #注意flag为True，表示node不能选择;False表示可选可不选
            if node is None:
                return 0
            
            if flag:
                #不选node
                res1 = dfs(node.left, False)
                res2 = dfs(node.right, False)
                return res1 + res2
            else:
                #不选node
                res1 = dfs(node.left, False)
                res2 = dfs(node.right, False)
                #选node
                res3 = dfs(node.left, True) 
                res4 = dfs(node.right, True)  
                return max(res1+res2,res3+res4+node.val)
        return max(dfs(root, False), dfs(root, True))    
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

题目24：121. 买卖股票的最佳时机

解题思路：动态规划。注意，只能交易一次。状态定义如下：
假设初始现金为0。
f[i][0]：第i天不持有股票的最大现金。
f[i][1]：第i天持有股票的最大现金。
状态初始化如下，
f[0][0] = 0
f[0][1] = -a[0]
状态转移如下，
f[i][0] = max(f[i-1][0], f[i-1][1] + a[i])
f[i][1] = max(f[i-1][1], f[i-1][0] && 从前没有买入股票 - a[i])，而f[i-1][0] && 从前没有买入股票也即第i-1天不持股并且从前没有买入股票，那么这种情况下现金必然为0。故f[i][1] = max(f[i-1][1], 0 - a[i])。
答案，
res = max(res, f[i][0])

C++代码如下，

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

python3代码如下，

class Solution:
    def maxProfit(self, a: List[int]) -> int:
        n = len(a)
        f = [[0,0] for _ in range(n)]
        f[0][0] = 0
        f[0][1] = -a[0]
        for i in range(1,n):
            f[i][0] = max(f[i-1][0], f[i-1][1]+a[i])
            f[i][1] = max(f[i-1][1], -a[i])
        res = 0
        for i in range(n):
            res = max(res, f[i][0])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

题目25：122. 买卖股票的最佳时机 II

解题思路如下：可以交易多次，动态规划求解。状态的定义同题目24，唯一的不同在于状态f[i][1]的转移方程上，f[i][1] = max(f[i-1][1], f[i-1][0] - a[i])。

C++代码如下，

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

python3代码如下，

class Solution:
    def maxProfit(self, a: List[int]) -> int:
        n = len(a)
        f = [[0,0] for _ in range(n)]
        f[0][0] = 0
        f[0][1] = -a[0]
        for i in range(1,n):
            f[i][0] = max(f[i-1][0], f[i-1][1]+a[i])
            f[i][1] = max(f[i-1][1], f[i-1][0]-a[i])
        res = 0
        for i in range(n):
            res = max(res, f[i][0])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

题目26：123. 买卖股票的最佳时机 III

解题思路：状态比较多，是一个状态机模型。状态定义如下：
f[i][0]：第i天，第0次不持股票的最大现金。
f[i][1]：第i天，第0次持股票的最大现金。
f[i][2]：第i天，第1次不持股票的最大现金。
f[i][3]：第i天，第1次持股票的最大现金。
f[i][4]：第i天，第2次不持股票的最大现金。
状态初始化如下：
f = [[-1e10] * 5 for _ in range(n)]
f[0][0] = 0
f[0][1] = -a[0]
状态转移如下：
f[i][0] = f[i-1][0]
f[i][1] = max(f[i-1][1], f[i-1][0] - a[i])
f[i][2] = max(f[i-1][2], f[i-1][1] + a[i])
f[i][3] = max(f[i-1][3], f[i-1][2] - a[i])
f[i][4] = max(f[i-1][4], f[i-1][3] + a[i])
最终答案如下：
res = max([res, f[i][0], f[i][2], f[i][4]])

C++代码如下，

class Solution {
public:
    int maxProfit(vector<int>& a) {
        int n = a.size();
        vector<vector<int>> f(n, vector<int>(5, -0x3f3f3f3f));
        f[0][0] = 0;
        f[0][1] = -a[0];
        int res = 0;
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i-1][0];
            f[i][1] = max(f[i-1][1], f[i-1][0] - a[i]);
            f[i][2] = max(f[i-1][2], f[i-1][1] + a[i]);
            f[i][3] = max(f[i-1][3], f[i-1][2] - a[i]);
            f[i][4] = max(f[i-1][4], f[i-1][3] + a[i]);
            res = max(res, f[i][0]);
            res = max(res, f[i][2]);
            res = max(res, f[i][4]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

python3代码如下，

class Solution:
    def maxProfit(self, a: List[int]) -> int:
        n = len(a)
        f = [[-1e10] * 5 for _ in range(n)]
        f[0][0] = 0
        f[0][1] = -a[0]
        res = 0
        for i in range(1,n):
            f[i][0] = f[i-1][0]
            f[i][1] = max(f[i-1][1], f[i-1][0] - a[i])
            f[i][2] = max(f[i-1][2], f[i-1][1] + a[i])
            f[i][3] = max(f[i-1][3], f[i-1][2] - a[i])
            f[i][4] = max(f[i-1][4], f[i-1][3] + a[i])  
            res = max([res, f[i][0], f[i][2], f[i][4]])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目27：188. 买卖股票的最佳时机 IV

解题思路如下：状态定义和转移同题目26。状态定义如下：
f[i][0]：第i天，第0次不持股票的最大现金。
f[i][1]：第i天，第0次持股票的最大现金。
f[i][2]：第i天，第1次不持股票的最大现金。
f[i][3]：第i天，第1次持股票的最大现金。
f[i][4]：第i天，第2次不持股票的最大现金。
……
f[i][2*k]：第i天，第k次不持股票的最大现金。

C++代码如下，

class Solution {
public:
    int maxProfit(int k, vector<int>& a) {
        int n = a.size();
        int m = 2 * k + 1;
        vector<vector<int>> f(n, vector<int>(m, -0x3f3f3f3f));
        f[0][0] = 0;
        f[0][1] = -a[0];
        int res = 0;
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i-1][0];
            for (int j = 1; j < m; ++j) {
                int sign = j % 2 == 1 ? -1 : 1;
                f[i][j] = max(f[i-1][j], f[i-1][j-1] + a[i] * sign);
                if (j % 2 == 0) {
                    res = max(res, f[i][j]);
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

python3代码如下，

class Solution:
    def maxProfit(self, k: int, a: List[int]) -> int:
        n = len(a)
        m = 2 * k + 1
        f = [[-1e10] * m for _ in range(n)]
        f[0][0] = 0
        f[0][1] = -a[0]
        res = 0
        for i in range(1,n):
            f[i][0] = f[i-1][0]
            for j in range(1,m):
                sign = -1 if j % 2 == 1 else 1
                f[i][j] = max(f[i-1][j], f[i-1][j-1] + a[i] * sign)
                if j % 2 == 0:
                    res = max(res, f[i][j])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第28题：309. 买卖股票的最佳时机含冷冻期

解题思路：状态定义如下，
f[i][0]：不持股票，恰好今天卖出，的最大现金。
f[i][1]：不持股票，冷冻期，的最大现金。
f[i][2]：不持股票，今天不卖出股票且不是冷冻期，的最大现金。
f[i][3]：持有股票。
状态初始化如下，
f = [-1e10] * 4 for _ in range(n)
f[0][2] = 0
f[0][3] = -a[0]
状态转移如下，
f[i][0] = f[i-1][3] + a[i]
f[i][1] = f[i-1][0]
f[i][2] = max(f[i-1][2], f[i-1][1])
f[i][3] = max([f[i-1][3], f[i-1][2]-a[i], f[i-1][1]-a[i]])，注意前一天是冷冻期，今天也可以买股票。
最终答案如下，
res = max([res, f[i][0], f[i][1], f[i][2]])

C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& a) {
        int n = a.size();
        vector<vector<int>> f(n, vector<int>(4, -0x3f3f3f3f));
        f[0][2] = 0;
        f[0][3] = -a[0];
        int res = 0;
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i-1][3] + a[i];
            f[i][1] = f[i-1][0];
            f[i][2] = max(f[i-1][2], f[i-1][1]);
            f[i][3] = max(f[i-1][3], f[i-1][2]-a[i]);
            f[i][3] = max(f[i][3], f[i-1][1]-a[i]);
            res = max(res, f[i][0]);
            res = max(res, f[i][1]);
            res = max(res, f[i][2]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

python3代码如下，

class Solution:
    def maxProfit(self, a: List[int]) -> int:
        n = len(a)
        f = [[-1e10] * 4 for _ in range(n)]
        f[0][2] = 0
        f[0][3] = -a[0]
        res = 0
        for i in range(1, n):
            f[i][0] = f[i-1][3] + a[i]
            f[i][1] = f[i-1][0]
            f[i][2] = max(f[i-1][2], f[i-1][1])
            f[i][3] = max([f[i-1][3], f[i-1][2]-a[i], f[i-1][1]-a[i]])
            res = max([res, f[i][0], f[i][1], f[i][2]])
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第29题：714. 买卖股票的最佳时机含手续费

解题思路如下：状态定义如下：
f[i][0]：第i天不持股的最大现金。
f[i][1]：第i天持股的最大现金。
fee在买入时扣除。
状态初始化如下：
f = [[-1e10] * 2 for _ in range(n)]
f[0][0] = 0
f[0][1] = -a[0] -fee
状态转移如下：
f[i][0] = max(f[i-1][0], f[i-1][1]+a[i])
f[i][1] = max(f[i-1][1], f[i-1][0]-a[i]-fee)
最终答案如下：
res = max(res, f[i][0])

C++代码如下：

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

python3代码如下：

class Solution:
    def maxProfit(self, a: List[int], fee: int) -> int:
        n = len(a)
        f = [[-1e10] * 2 for _ in range(n)]
        f[0][0] = 0
        f[0][1] = -a[0]-fee 
        res = 0
        for i in range(1,n):
            f[i][0] = max(f[i-1][0], f[i-1][1]+a[i])
            f[i][1] = max(f[i-1][1], f[i-1][0]-a[i]-fee)
            res = max(res, f[i][0])
        return res 
1
2
3
4
5
6
7
8
9
10
11
12

第30题：300. 最长递增子序列

解题思路如下：状态定义如下：
f[i]：以a[i]结尾的递增子序列，长度max。
状态初始化如下：
f = [1] * n
状态转移如下：

for i in range(n):
	for j in range(i):
		if a[j] < a[i]:
			f[i] = max(f[i], f[j]+1)
1
2
3
4

最终答案如下：
max(f)
C++代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& a) {
        int n = a.size();
        vector<int> f(n, 1);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (a[j] < a[i]) {
                    f[i] = max(f[i], f[j]+1);
                }
            }
            res = max(res, f[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

python3代码如下，

class Solution:
    def lengthOfLIS(self, a: List[int]) -> int:
        n = len(a)
        f = [1] * n 
        for i in range(n):
            for j in range(i):
                if a[j] < a[i]:
                    f[i] = max(f[i], f[j]+1)
        return max(f)
1
2
3
4
5
6
7
8
9

第31题：674. 最长连续递增序列

解题思路：状态定义如下：
f[i]：以a[i]结尾的连续递增数组的最大长度。
状态初始化如下：
f = [1] * n
状态转移如下：
f[i] = f[i-1]+1 if a[i-1] < a[i] else 1
最终结果如下：
max(f)
C++代码如下，

class Solution {
public:
    int findLengthOfLCIS(vector<int>& a) {
        int n = a.size();
        vector<int> f(n, 1);
        int res = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i-1] < a[i]) {
                f[i] = f[i-1] + 1;
            }
            res = max(res, f[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python3代码如下，

class Solution:
    def findLengthOfLCIS(self, a: List[int]) -> int:
        n = len(a)
        f = [1] * n 
        for i in range(1,n):
            if a[i-1] < a[i]:
                f[i] = f[i-1] + 1
        return max(f)
1
2
3
4
5
6
7
8

第32题：718. 最长重复子数组

解题思路：状态定义如下，
f[i][j]：以a[i]结尾的子数组，以b[j]结尾的子数组，最长重复子数组。
状态初始化如下，
f[0][j] = int(a[0] == b[j])
f[i][0] = int(a[i] == b[0])
状态转移如下，

if a[i] == b[j]:
	f[i][j] = max(f[i][j], f[i-1][j-1]+1)
1
2

最终答案如下，
res = max(res, f[i][j])
C++代码如下，

class Solution {
public:
    int findLength(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        vector<vector<int>> f(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            f[i][0] = a[i] == b[0];
        }
        for (int j = 0; j < m; ++j) {
            f[0][j] = a[0] == b[j];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (a[i] == b[j]) {
                    f[i][j] = f[i-1][j-1]+1;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                res = max(res, f[i][j]);
            }
        }
        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

python3代码如下，

class Solution:
    def findLength(self, a: List[int], b: List[int]) -> int:
        n = len(a)
        m = len(b)
        f = [[0] * m for _ in range(n)]
        for i in range(n):
            f[i][0] = int(a[i] == b[0])
        for j in range(m):
            f[0][j] = int(a[0] == b[j])
        for i in range(1,n):
            for j in range(1,m):
                if a[i] == b[j]:
                    f[i][j] = f[i-1][j-1]+1
        res = 0
        for i in range(n):
            for j in range(m):
                res = max(res, f[i][j])
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第33题：1143. 最长公共子序列

解题思路如下：前处理如下，
a = '#' + a
b = '#' + b
状态定义如下，
f[i][j]：a[1:i]和b[1:j]的最长公共子序列。
状态初始化如下，
f = [[0] * m for _ in range(n)]
状态转移如下，

if a[i] == b[j]:
	f[i][j] = max(f[i][j], f[i-1][j-1]+1)
else:
	f[i][j] = max(f[i-1][j], f[i][j-1])
1
2
3
4

最终结果如下，
f[n-1][m-1]

C++代码如下：

class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
        a = "#" + a;
        b = "#" + b;
        int n = a.size();
        int m = b.size();
        vector<vector<int>> f(n, vector<int>(m, 0));
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (a[i] == b[j]) {
                    f[i][j] = max(f[i][j], f[i-1][j-1]+1);
                } else {
                    f[i][j] = max(f[i-1][j], f[i][j-1]);
                }
            }
        }
        return f[n-1][m-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

python3代码如下，

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        a = '#' + a
        b = '#' + b
        n = len(a)
        m = len(b)
        f = [[0] * m for _ in range(n)]
        for i in range(1,n):
            for j in range(1,m):
                if a[i] == b[j]:
                    f[i][j] = max(f[i][j], f[i-1][j-1]+1)
                else:
                    f[i][j] = max(f[i-1][j], f[i][j-1])
        return f[n-1][m-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第34题：1035. 不相交的线

解题思路如下：最长公共子序列模型。

C++代码如下，

class Solution {
public:
    int maxUncrossedLines(vector<int>& a, vector<int>& b) {
        a.insert(a.begin(), -1);
        b.insert(b.begin(), -1);
        int n = a.size();
        int m = b.size();
        vector<vector<int>> f(n, vector<int>(m, 0));
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                if (a[i] == b[j]) {
                    f[i][j] = f[i-1][j-1]+1;
                } else {
                    f[i][j] = max(f[i-1][j], f[i][j-1]);
                }
            }
        }
        return f[n-1][m-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

python3代码如下，

class Solution:
    def maxUncrossedLines(self, a: List[int], b: List[int]) -> int:
        a.insert(0, -1)
        b.insert(0, -1)
        n = len(a)
        m = len(b)
        f = [[0] * m for _ in range(n)]
        for i in range(1,n):
            for j in range(1,m):
                if a[i] == b[j]:
                    f[i][j] = f[i-1][j-1]+1
                else:
                    f[i][j] = max(f[i-1][j], f[i][j-1])
        return f[n-1][m-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第35题：53. 最大子数组和

解题思路：状态定义如下，
f[i]：以a[i]结尾的子数组，和最大。
状态初始化如下，
f = copy.deepcopy(a)
状态转移如下，
f[i] = max(f[i], f[i-1]+a[i])
最终答案如下，
max(f)
C++代码如下，

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

python3代码如下，

class Solution:
    def maxSubArray(self, a: List[int]) -> int:
        n = len(a)
        f = []
        for i in range(n):
            f.append(a[i])
        for i in range(1,n):
            f[i] = max(f[i], f[i-1]+a[i])
        return max(f)
1
2
3
4
5
6
7
8
9

第36题：392. 判断子序列

解题思路如下：贪心，子序列的下标增长得越慢越好，后面才有选择的空间。

C++代码如下，

class Solution {
public:
    bool isSubsequence(string s, string t) {
        unordered_map<char, vector<int>> map_c_idxs;
        for (int i = 0; i < t.size(); ++i) {
            map_c_idxs[t[i]].emplace_back(i);
        }
        int preidx = -1;
        for (auto c : s) {
            if (map_c_idxs.count(c) == 0) {
                return false;
            } else {
                vector<int> idxs = map_c_idxs[c];
                auto it = upper_bound(idxs.begin(), idxs.end(), preidx);
                if (it == idxs.end()) {
                    return false;
                } else {
                    preidx = *it;
                }
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

python3代码如下，

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        map_c_idxs = collections.defaultdict(list)
        for i,c in enumerate(t):
            map_c_idxs[c].append(i)
        preidx = -1
        for c in s:
            if c not in map_c_idxs:
                return False 
            else:
                idxs = map_c_idxs[c]
                j = bisect.bisect_right(idxs, preidx)
                if j < len(idxs):
                    preidx = idxs[j]
                else:
                    return False 
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第37题：115. 不同的子序列

解题思路：状态定义如下，
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数。也即s[0:i]中以s[i-1]结尾的子序列中出现t[0:j]的个数。
状态初始化如下，

f = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
	f[i][0] = 1
for j in range(1,m+1):
	f[0][j] = 0
1
2
3
4
5

状态转移如下，

if s[i-1] == t[j-1]:
	dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else:
	dp[i][j] = d[i-1][j]
1
2
3
4

最终答案如下，
f[n][m]

C++代码如下，

class Solution {
public:
    const int mod = 1e9 + 7;

    int numDistinct(string s, string t) {
        int n = s.size();
        int m = t.size();
        vector<vector<int>> f(n+1, vector<int>(m+1, 0));
        for (int i = 0; i < n+1; ++i) {
            f[i][0] = 1;
        }
        for (int j = 1; j < m+1; ++j) {
            f[0][j] = 0;
        }
        for (int i = 1; i < n+1; ++i) {
            for (int j = 1; j < m+1; ++j) {
                if (s[i-1] == t[j-1]) {
                    f[i][j] = f[i-1][j-1] + f[i-1][j];
                } else {
                    f[i][j] = f[i-1][j];
                }
                f[i][j] %= mod;
            }
        }
        return f[n][m];
    }
};
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

python3代码如下，

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)
        f = [[0] * (m+1) for _ in range(n+1)]
        for i in range(n+1):
            f[i][0] = 1
        for j in range(1,m+1):
            f[0][j] = 0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if s[i-1] == t[j-1]:
                    f[i][j] = f[i-1][j-1] + f[i-1][j]
                else:
                    f[i][j] = f[i-1][j]
        return f[n][m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第38题：583. 两个字符串的删除操作

解题思路如下：最长公共子序列模型。

C++代码如下，

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size();
        int m = b.size();
        vector<vector<int>> f(n+1,vector<int>(m+1,0));
        for (int i = 1; i < n+1; ++i) {
            for (int j = 1; j < m+1; ++j) {
                if (a[i-1] == b[j-1]) {
                    f[i][j] = f[i-1][j-1]+1;
                } else {
                    f[i][j] = max(f[i-1][j], f[i][j-1]);
                }
            }
        }
        return n-f[n][m] + m-f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

python3代码如下，

class Solution:
    def minDistance(self, a: str, b: str) -> int:
        n = len(a)
        m = len(b)
        f = [[0] * (m+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                if a[i-1] == b[j-1]:
                    f[i][j] = f[i-1][j-1]+1
                else:
                    f[i][j] = max(f[i-1][j], f[i][j-1])
        commonlength = f[n][m]
        res = n + m - commonlength * 2
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第39题：72. 编辑距离

解题思路如下，状态定义如下，
f[i][j]：a[0:i]和b[0:j]的最小编辑距离。
状态初始化如下，

f = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
	f[i][0] = i
for j in range(m+1):
	f[0][j] = j 
1
2
3
4
5

状态转移如下，

if a[i-1] == b[j-1]:
	f[i][j] = f[i-1][j-1]
else:
	f[i][j] = max([f[i-1][j-1], f[i-1][j], f[i][j-1]]) + 1
1
2
3
4

最终答案如下，
f[n][m]

C++代码如下，

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.size();
        int m = b.size();
        vector<vector<int>> f(n+1,vector<int>(m+1, 0));
        for (int i = 0; i < n+1; ++i) {
            f[i][0] = i;
        }
        for (int j = 0; j < m+1; ++j) {
            f[0][j] = j;
        }
        for (int i = 1; i < n+1; ++i) {
            for (int j = 1; j < m+1; ++j) {
                if (a[i-1] == b[j-1]) {
                    f[i][j] = f[i-1][j-1];
                } else {
                    f[i][j] = min(f[i-1][j-1]+1, f[i-1][j]+1);
                    f[i][j] = min(f[i][j], f[i][j-1]+1);
                }
            }
        }
        return f[n][m];
    }
};
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

python3代码如下，

class Solution:
    def minDistance(self, a: str, b: str) -> int:
        n = len(a)
        m = len(b)
        f = [[0] * (m+1) for _ in range(n+1)]
        for i in range(n+1):
            f[i][0] = i 
        for j in range(m+1):
            f[0][j] = j 
        for i in range(1,n+1):
            for j in range(1,m+1):
                if a[i-1] == b[j-1]:
                    f[i][j] = f[i-1][j-1]
                else:
                    f[i][j] = min([f[i-1][j-1], f[i-1][j], f[i][j-1]]) + 1
        return f[n][m]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第40题：647. 回文子串

解题思路如下：状态定义如下，
f[i][j]：区间[i,j]的子串是不是回文串。
由如上状态定义可知，j >= i。
状态初始化如下，

f = [[False] * n for _ in range(n)]
1

状态转移如下，

if s[i] != s[j]:
	f[i][j] = False
else:
	if  j - i <= 1:
		f[i][j] = True 
	else:
		f[i][j] = f[i+1][j-1]
1
2
3
4
5
6
7

根据状态转移方程可知，遍历i时，需要从大到小，遍历j时，需要从小到大。

最终答案如下，

res = 0
for i in range(n):
	for j in range(m):
		if f[i][j] == True:
			res += 1
1
2
3
4
5

C++代码如下，

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<int>> f(n, vector<int>(n, false));
        for (int i = n-1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] != s[j]) {
                    f[i][j] = false;
                } else {
                    if (j - i <= 1) {
                        f[i][j] = true;
                    } else {
                        f[i][j] = f[i+1][j-1];
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (f[i][j]) res += 1;
            }
        }
        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

python3代码如下，

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        f = [[False] * n for _ in range(n)]
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] != s[j]:
                    f[i][j] = False 
                else:
                    if j - i <= 1:
                        f[i][j] = True 
                    else:
                        f[i][j] = f[i+1][j-1]
        res = 0
        for i in range(n):
            for j in range(n):
                if f[i][j]:
                    res += 1
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第41题：516. 最长回文子序列

解题思路：状态定义如下，
f[i][j]：字符串s在[i,j]范围内的回文子序列的最大长度。
状态初始化如下，

f = [[0] * n for _ in range(n)]
1

状态转移如下，

if s[i] != s[j]:
	f[i][j] = max(f[i+1][j], f[i][j-1])
else:
	if i == j:
		f[i][j] = 1
	else:
		f[i][j] = f[i+1][j-1] + 2
1
2
3
4
5
6
7

由上可知，遍历i时需从大到小，遍历j时需从小到大。

最终答案如下，
f[0][n-1]
C++代码如下：

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> f(n, vector<int>(n, 0));
        for (int i = n-1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] != s[j]) {
                    f[i][j] = max(f[i][j-1], f[i+1][j]);
                } else {
                    if (i == j) f[i][j] = 1;
                    else f[i][j] = f[i+1][j-1] + 2;
                }
            }
        }
        return f[0][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

python3代码如下，

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] != s[j]:
                    f[i][j] = max(f[i+1][j], f[i][j-1])
                else:
                    if i == j:
                        f[i][j] = 1
                    else:
                        f[i][j] = f[i+1][j-1] + 2
        return f[0][n-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3 参考

代码随想录官网

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/1020085

代码随想录leetcode200题之动态规划算法

目录

1 介绍

2 训练

3 参考