菜鸟追梦旅行

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

热门标签

代码随想录1刷--day9 动态规划

作者：菜鸟追梦旅行 | 2024-04-09 04:48:57

踩

代码随想录1刷--day9 动态规划

动态规划

基础题目
- 509 斐波那契数
- 70 爬楼梯
- 746 使用最小花费爬楼梯
- 62 不同路径
- 63 不同路径II
- 343 整数拆分
- 96 不同的二叉搜索树
背包问题
- 01背包
  - 0416 分割等和子集
  - 1049 最后一块石头的重量II
  - 0494 目标和
  - 0474 一和零
- 完全背包
  - 0518 零钱兑换II
  - 0377 组合总和IV
  - 0070 爬楼梯
  - 0322 零钱兑换
  - 0279 完全平方数
  - 0139 单词拆分
- 多重背包
打家劫舍
- 198 打家劫舍
- 213 打家劫舍II
- 337 打家劫舍III
股票问题
- 121 买卖股票的最佳时机(只能买买一次)
- 122 买卖股票的最佳时机II(可以买卖多次)
- 123 买卖股票的最佳时机III(最多买卖两次)
- 188 买卖股票的最佳时机IV(最多买卖k次)
- 309 买卖股票的最佳时期含冷冻期(T+1)
- 714 买卖股票的最佳时机含手续费(买卖多次，每次有手续费)
子序列问题
- 子序列(不连续)
  - 300 最长上升子序列
  - 1143 最长公共子序列
  - 1035 不相交的线
- 子序列(连续)
  - 674 最长连续递增序列
  - 718 最长重复子数组
  - 53 最大子序和
- 编辑距离
  - 392 判断子序列
  - 115 不同的子序列
  - 583 两个字符串的删除操作
  - 72 编辑距离
- 回文
  - 647 回文子串
  - 516 最长回文子串

动态规划理论基础

动态规划，英文：Dynamic Programming, 简称DP，如果某个问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的。

动态规划的解题步骤（动态规划五部曲）

确定dp数组以及下标含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

基础题目

509 斐波那契数列

// 1. 确定dp数组以及下标含义：dp[i]定义为第i个数的值为dp[i]
// 2. 确定递推公式:dp[i] = dp[i-1]+dp[i-2]
// 3. dp数组如何初始化: dp[0]=0; dp[1]=1;
// 4. 确定遍历顺序:从前往后遍历
// 5. 举例推导dp数组
class Solution {
public:
    int fib(int n) {
        if(n<=1) return n;
        // vector<int> dp(n+1);
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++)
        {
            // dp[i] = dp[i-1] + dp[i-2];
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;

        }
        // return dp[n];
        return dp[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

70 爬楼梯

// 1. 确定dp数组以及下标含义:dp[i]:爬到第i层有dp[i]种方法
// 2. 确定递推公式dp[i] =  dp[i-1]+dp[i-2]
// 3. dp数组如何初始化， dp[1]=1;dp[2]=2;
// 4. 确定遍历顺序，从前往后遍历
// 5. 举例推导dp数组
class Solution {
public:
    int climbStairs(int n) {
        if(n<=1) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        for(int i=3; i<=n; i++)
        {
            int sum = dp[1] + dp[0];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

746 使用最小花费爬楼梯

// 1. 确定dp数组以及下标含义：dp[i]的定义，到达第i台阶花费的最少体力
// 2. 确定递推公式：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
// 3. dp数组如何初始化:dp[0]=0, dp[1]=0;
// 4. 确定遍历顺序，从前往后遍历
// 5. 举例推导dp数组
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1);
        dp[0] = 0;
        dp[1] = 0;
        for(int i=2; i<dp.size(); i++)
        {
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

62 不同路径

// 1. 确定dp数组以及下标含义：dp[i][j]表示从(0,0)出发，到(i,j)有dp[i][j]条路径
// 2. 确定递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]
// 3. dp数组如何初始化:dp[i][0]=1; dp[0][j]=1;
// 4. 确定遍历顺序：从左到右一层一层遍历
// 5. 举例推导dp数组
// 时间复杂度O(m*n)
// 空间复杂度O(m*n)
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n,0));
        for(int i=0; i<m; i++)  dp[i][0]=1;
        for(int i=0; i<n; i++)  dp[0][i]=1;
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

63 不同路径II

// 1. 确定dp数组以及下标含义：dp[i][j]表示从(0,0)出发，到(i,j)有dp[i][j]条路径
// 2. 确定递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]
// 3. dp数组如何初始化:dp[i][0]=1; dp[0][j]=1;其他的初始化为0
// 4. 确定遍历顺序：从左到右一层一层遍历，遇到障碍物则跳过，因为初始化是0，所以不影响递推公式
// 5. 举例推导dp数组
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n,0));
        for(int i=0; i<m; i++)
        {
            if(obstacleGrid[i][0]==1)
                break;
            dp[i][0]=1;
        }
        for(int i=0; i<n; i++)
        {
            if(obstacleGrid[0][i]==1)
                break;
            dp[0][i]=1;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-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

343 整数拆分

// 1. 确定dp数组以及下标含义：dp[i]:分拆数字i，得到的最大的乘积为dp[i]
// 2. 确定递推公式， dp[i]=max(dp[i], (i-j)*j, dp[i-j]*j)。dp[i]是为了获得各种j拆分下的乘积最大值
// 3. dp数组如何初始化，dp[2]=1;
// 4. 确定遍历顺序， 从前往后遍历
// 5. 举例推导dp数组
// 时间复杂度O(n²)
// 空间复杂度O(n)
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        dp[2] = 1;
        for(int i=3; i<=n; i++){
            for(int j=1; j<=i/2; j++){
                dp[i] = max(max(j*(i-j), dp[i-j]*j), dp[i]);    // 注意max接收两个参数
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

96 不同的二叉搜索树

// 1. 确定dp数组以及下标含义：dp[i]：i对应的二叉搜索树的数量,j表示以j为根节点
// 2. 确定递推公式，dp[i]+=dp[j-1]*dp[i-j],遍历j。左子树的元素个数是j-1,右子树的元素个数是i-j
// 3. dp数组如何初始化,dp[0]=1
// 4. 确定顺序，i从1-n，j从1到i
// 5. 举例推导dp数组
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
14
15
16
17
18

背包问题

01背包

46 携带研究材料（卡码网:https://kamacoder.com/problempage.php?pid=1046）(二维dp数组实现)

// 确定dp数组以及其下标含义，dp[i][j]表示在下标为[0-i]的物品里任选，放入容量为j的背包得到的最大价值
// 确定递推公式，dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
// dp数组初始化，dp[i][0]=0,dp[0][j]=value[0],>=weight[0]
// 确定顺序，逐层即可

#include<bits/stdc++.h>
using namespace std;

int n, bagweight;   // bagweight是行李箱空间
void solve(){
    vector<int> weight(n,0);
    vector<int> value(n,0);
    for(int i=0; i<n; i++)
    {
        cin>>weight[i];
    }
    for(int j=0; j<n; j++)
    {
        cin>>value[j];
    }
    
    // dp数组
    vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1, 0));
    
    // dp数组初始化
    for(int j=weight[0]; j<=bagweight;j++){
        dp[0][j] = value[0];
    }
    
    // 遍历
    for(int i=1; i<weight.size();i++){
        for(int j=0; j<=bagweight; j++){
            if(j<weight[i]) dp[i][j] = dp[i-1][j];
            else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
            }
        }
    }
    cout<<dp[weight.size()-1][bagweight]<<endl;
}

int main(){
    while(cin>>n>>bagweight){
        solve();
    }
    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

01背包问题滚动数组实现(一维dp数组)
由递推公式dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
dp[i][j]完全用的是上一层的数据，因此可以用一个一维数组来实现dp[j]
递推公式：dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
初始化：dp[0]=0
遍历顺序：外层从前往后，内层从后往前:原因是需要用到上一层和左侧的值，从右向左才能用到左侧的旧值，从左往右旧值会被覆盖，结果就是同一个物品被放多次

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;

int main(){
    // 读取M，N
    int M,N;
    cin>>M>>N;
    
    vector<int> costs(M);
    vector<int> values(M);
    
    for(int i=0; i<M; i++){
        cin >> costs[i];
    }
    for(int j=0; j<M;j++){
        cin >> values[j];
    }
    
    // 一维dp数组
    vector<int> dp(N+1, 0);
    
    // 外层循环遍历物品
    for(int i=0; i<M; i++){
        // 内层循环从N空间逐渐减小到当前物品需要的空间
        for(int j=N; j>=costs[i]; j--){
            dp[j] = max(dp[j], dp[j-costs[i]]+values[i]);
        }
    }
    
    cout << dp[N] << endl;
}

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

416 分割等和子集

// 01背包问题，在集合中找出元素和等于sum的一半，也即容量为sum/2的背包能否装满
// 定义dp数组，dp[j]:容量为j的背包能装的最大价值; 装满时dp[target]==target
// 状态转移方程： dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
// dp数组初始化dp[0]=0
// 
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int& i : nums)
            sum+=i;
        if(sum%2)   return false;
        int target = sum/2;
        vector<int> dp(target+1, 0);
        for(int i=0; i<nums.size(); i++){
            for(int j=target; j>=nums[i]; j--){
                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target]==target) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1049 最后一块石头的重量II

// 思路是尽量把石头分成重量和接近的两堆， 所以还是一个01背包问题
// 定义dp数组，dp[j]:容量为j的背包能装的最大的石头重量
// 状态转移方程， dp[j]=max(dp[j], dp[j-stones[i]]]+stones[i])
// dp数组初始化 dp[0]=0;
// 遍历顺序外层循环遍历石头，内存循环从后往前遍历空间
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int& i:stones)
            sum+=i;
        int target = sum/2;
        vector<int> dp(target+1,0);
        for(int i=0; i<stones.size(); i++){
            for(int j=target; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

494 目标和

// 思路是假设正数之和是x，负数之和是y，x+y=sum, x-y=target, x = (sum+target)/2
// 那么就变成了一个背包问题，有多少种组合能够满足和为x
// 定义dp数组，dp[j]装满背包容量为j的背包有dp[j]种方法
// 状态转移方程； 来看凑成dp[4]有多少种方法：dp[4]=dp[3]凑成(+1)+dp[2]凑成(+2)+dp[1]凑成(+3)+dp[0]凑成+4
// 归纳为：dp[j]+=dp[j-nums[i]]
// dp数组初始化：dp[0]=1,因为背包容量为4，刚好有数字4，那就是有1种方法
// 遍历顺序，
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int& i:nums){
            sum+=i;
        }
        if((target+sum)%2 || abs(target)>sum) return 0; // 这里要注意abs(target)>sum的情况
        int c = (target+sum)/2;

        vector<int> dp(c+1,0);
        dp[0]=1;
        for(int i=0; i<nums.size(); i++){
            for(int j=c; j>=nums[i]; j--)
            {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[c];
    }
};
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

474 一和零
两个维度上的01背包问题

// 两个维度的背包，能装m个0和n个1
// 定义dp数组，dp[i][j]表示容量为i个0，j个1的背包最多有dp[i][j]个物品
// num0和num1分别代表了该字符串包含的0的个数和1的个数
// 状态转移方程，dp[i][j] = max(dp[i][j], dp[i-num0][j-num1])
// 初始化dp数组，初始化为0

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {

        vector<vector<int>> dp(m+1, vector<int>(n+1,0));
        for(string& str:strs){  // 遍历字符串
            int num0=0, num1=0;
            for(char& c:str){
                if(c=='0')  num0++;
                else    num1++;
            }
            for(int i=m; i>=num0; i--){ // 遍历背包
                for(int j=n; j>=num1; j--){
                    dp[i][j] = max(dp[i][j], dp[i-num0][j-num1]+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
24
25
26

完全背包

理论基础：有N件物品和最多能背重量为W的背包，第i件物品的重量为weight[i]，得到的价值为value[i]，每件物品都有无限个。求解背包能装下的最大价值
完全背包问题与01背包问题的区别在于，同一个物品是可以被多次选择的，在前面01背包问题中提到，对背包容量是从大到小遍历，这就是为了防止同一个物品被多次选择。
因此在完全背包问题中，只需要将对背包容量的遍历也变成从小到大即可

完全背包问题：https://kamacoder.com/problempage.php?pid=1052

#include <iostream>
#include <vector>

using namespace std;

void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight){
    vector<int> dp(bagWeight+1, 0);
    
    for(int i=0; i<weight.size();i++){ // 遍历物品
        for(int j=0; j<=bagWeight; j++){    // 遍历背包容量
            if(j - weight[i] >= 0)
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

int main(){
    int N, V;
    cin >>N >>V;
    vector<int> weight;
    vector<int> value;
    
    for(int i=0; i<N; i++){
        int w,v;
        cin>>w>>v;
        weight.push_back(w);
        value.push_back(v);
    }
    
    test_CompletePack(weight, value, V);
    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

518 零钱兑换II
注意这题循环的顺序不能变

// 完全背包问题
// dp[j]，表示总金额为j对应的组合次数
// 状态转移方程：dp[j] += dp[j-coins[i]]    // 所有dp[j-coins[i]]相加
// 初始化：dp[0]=1;
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(int i=0; i<coins.size(); i++){  // 遍历硬币
            for(int j=coins[i]; j<=amount; j++){    // 遍历
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

// 关于遍历顺序：
// 先遍历物品是组合 先遍历背包是排列 求价值排列组合求和都一样 
// 求多少种方法排列数比组合数多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

377 组合总和IV

// 这题和零钱兑换II几乎相同，区别在于这里是排列，不同顺序的组合不同
// 前面讲到，先遍历背包再遍历物品得到的就是排列数
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for(int j=0; j<=target; j++){   // 先遍历背包，后遍历物体，得到的就是排列数
            for(int i=0; i<nums.size(); i++){
                if(j>=nums[i] && dp[j]<INT_MAX-dp[j-nums[i]])
                    dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

爬楼梯进阶版：https://kamacoder.com/problempage.php?pid=1067
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> dp(n+1,0);
    dp[0]=1;
    for(int j=1; j<=n; j++){        // 注意i和j不是索引，应该从1开始
        for(int i=1; i<=m; i++){
            if(j>=i)    dp[j] += dp[j-i];   
        }
    }
    cout << dp[n] <<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

322 零钱兑换

// dp[j]: 凑成总额为j的硬币最小个数为dp[j]
// 凑成j-coins[i]所需要的最小硬币数为dp[j-coins[i]]
// 那么+1就可以得到dp[j]，那么dp[j]就是所有的dp[j-coins[i]]+1中最小的
// dp[j] = min(dp[j], dp[j-coins[i]]+1);
// 初始化，dp[0]=0；
// 遍历顺序，无影响
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0] = 0;
        for(int i=0; i<coins.size(); i++){
            for(int j=coins[i]; j<=amount;j++){
                if(dp[j-coins[i]] != INT_MAX) 
                    dp[j] = min(dp[j], dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX? -1:dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

279 完全平方数

// 也是一个多重背包问题，因为每个数字可以重复使用
// 有那些数字呢？1到100的平方
// dp[j]，凑成100的完全平方数的个数
// dp[j] = min(dp[j], dp[j-nums[i]]+1)
// 初始化为INT_MAX
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        for(int i=1; i<=100; i++){
            for(int j=i*i; j<=n; j++){
                dp[j] = min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

139 单词拆分

// dp[i]: 长度为i的字符串能否被子串组成，true/false
// dp[i] = dp[j~i] && dp[j],就是说dp[i]可以由子串组成，并且分割出来的部分也是一个字串
// 初始化dp[0]=true，其他初始化为false
// 这是一个排列问题，先遍历背包，再遍历物品
// 时间复杂度：O(n^3), 因为substr返回子串的副本是O(n)的复杂度（这里的n是substring的长度）
// 空间复杂度：O(n)
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1, false);
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        dp[0] = true;
        for(int i=1; i<=s.size(); i++){
            for(int j=0; j<i; j++){
                string word = s.substr(j,i-j);  // 分割子串
                if(wordSet.find(word)!=wordSet.end() && dp[j])
                    dp[i] = true;
            }
        }
        return dp[s.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

打家劫舍

198 打家劫舍

// 思路：当前房间能不能偷取决于前一个房间有没有偷
// 考虑下标i，能偷到的最大金额是dp[i],最终结果是dp[nums.size()-1]
// dp[i] = max(nums[i]+dp[i-2], dp[i-1]), 偷i和不偷i的最大金额
// 初始化，dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);   // 注意这里用了nums[1]，要避免越界
        
        for(int i=2; i<nums.size(); i++)
            dp[i] = max(nums[i]+dp[i-2], dp[i-1]);
        
        return dp[nums.size()-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

213 打家劫舍II

// 这道题相较于198区别在于数组的首尾是相邻的
// 想法是拆成两个数组来做,不包含头数字和不包含尾数字的，后面的做法就和198一样了
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        int result1 = robRange(nums, 0, nums.size()-2);
        int result2 = robRange(nums, 1, nums.size()-1);
        return max(result1, result2);
    }

    int robRange(const vector<int>& nums, int start, int end){
        if(end==start) return nums[end];
        vector<int> dp(nums.size(), 0);
        dp[start] = nums[start];
        dp[start+1] = max(nums[start], nums[start+1]);
        for(int i=start+2; i<=end; i++){
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[end];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

337 打家劫舍III
这是树形dp的第一题，dp数组包含两个元素,dp[0]当前节点不偷的最大值，dp[1]当前节点偷的最大值，采用后序遍历，还是挺难的

/**
 * 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) {}
 * };
 */
 // 当前节点的两个状态，偷(则最大金额=sum(子节点不偷)+value), 不偷(则最大金额=sum(max(子节点偷或者不偷)))
 // 定义dp数组dp[0]当前节点不偷的最大金额，dp[1]当前节点偷的最大金额
 // 遍历顺序：后序遍历
 
class Solution {
private:
    vector<int> robTree(TreeNode* cur){
        if(cur==nullptr) return vector<int>{0,0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷当前节点, 则子节点不能偷
        int var1 = cur->val + left[0] + right[0];
        // 当前节点不偷
        int var2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {var2, var1};
}
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[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

股票问题

121 买卖股票的最佳时机

// 定义dp数组，dp[i][0]表示在第i天持有股票的最大收益，dp[i][1]标识第i天没有持股的最大收益
// 上面两种状态确定是没有遗漏的
// dp[i][0] = max(-prices[i], dp[i-1][0]) 今天买的还是之前买的
// dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])  当天卖出还是早就已经卖出
// 初始化dp[0][0] = -prices[0], dp[0][1] = 0;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<len; i++){
            dp[i][0] = max(-prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }
        return dp[len-1][1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

122 买卖股票的最佳时机II（多次买卖）
这道题前面用贪心解决过，即把正利润叠加得到，这里用动态规划重新解决，和上一题的区别在于可以多次买卖，这样本次买的时候利润就不是从0开始算了

// 定义dp数组，dp[i][0]表示在第i天持有股票的最大收益，dp[i][1]标识第i天没有持股的最大收益
// dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0]) 今天买的还是之前买的
// dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])  当天卖出还是早就已经卖出
// 初始化dp[0][0] = -prices[0], dp[0][1] = 0;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i=1; i<len; i++){
            dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }
        return dp[len-1][1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

123 买卖股票的最佳时机III

// dp[i][0] 无操作， dp[i][1] 第一次持有 dp[i][2]第一次不持有(指卖出过),dp[i][3]第二次持有， dp[i][4]第二次不持有
// 所以dp数组一定要能不遗漏地描述所有的状态
// dp[i][0] = dp[i-1][0];
// dp[i][1] = max(dp[i-1][1], -prices[i]);  // 之前买的还是今天买的？
// dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]); // 今天卖的还是之前卖的
// dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]) //之前买的还是今天买的？ 
// dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4])   // 今天卖的还是之前卖的？

// 初始化 dp[0][0]=0 dp[0][1] = -prices[0]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(5,0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];  // 理解为第一天买入卖出买入， 这步非常重要
        for(int i=1; i<len; i++)
        {
            // dp[i][0] = dp[i-1][0];
            dp[i][1] = max(dp[i-1][1], -prices[i]);
            dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]);
            dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        return dp[len-1][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

188 买卖股票的最佳时机IV

// 这道题是123买卖两次的进阶，用相同的思路解决
// dp[i][0] 无操作， dp[i][1] 第一次持有 dp[i][2]第一次不持有(指卖出过),
// dp[i][3]第二次持有， dp[i][4]第二次不持有，以此类推， dp数组到dp[i][2*k]
// 状态转移方程：
// dp[i][0] = dp[i-1][0];
// dp[i][1] = max(dp[i-1][1], -prices[i]);  // 之前买的还是今天买的？
// dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2]); // 今天卖的还是之前卖的
// dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]) //之前买的还是今天买的？ 
// dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4])   // 今天卖的还是之前卖的？
// ...
// dp[i][2*k-1] = max(dp[i-1][2*k-1], dp[i-1][2*k-2]-prices[i]) //之前买的还是今天买的？ 
// dp[i][2*k] = max(dp[i-1][2*k-1]+prices[i], dp[i-1][2*k])   // 今天卖的还是之前卖的？
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2*k+1, 0));
        for(int i=1; i<=k; i++){
            dp[0][2*i-1] = -prices[0];
        }

        for(int i=1; i<len; i++)
        {
            for(int j=1; j<=k; j++){
                dp[i][2*j-1] = max(dp[i-1][2*j-1], dp[i-1][2*j-2]-prices[i]);
                dp[i][2*j] = max(dp[i-1][2*j-1]+prices[i], dp[i-1][2*j]);
            }
        }
        return dp[len-1][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
24
25
26
27
28
29
30
31

309 买卖股票的最佳时期含冷冻期(卖出第二天不能买入)

// dp[i][0] 持有股票，dp[i][1] 不持有，非冷冻期， dp[i][2] 当天卖出股票, dp[i][3] 冷冻期
// dp[i][0] = max(dp[i-1][0], dp[i-1][3]-prices[i], dp[i-1][1]-prices[i]); 当天持有包含这三种情况
// dp[i][1] = max(dp[i-1][1], dp[i-1][3])
// dp[i][2] = dp[i-1][0]+prices[i]
// dp[i][3] = dp[i-1][2]
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len==1) return 0;
        vector<vector<int>> dp(len, vector<int>(4,0));
        dp[0][0] = -prices[0];
        for(int i=1; i<len; i++)
        {
            dp[i][0] = max(max(dp[i-1][0], dp[i-1][3]-prices[i]), dp[i-1][1]-prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][3]);
            dp[i][2] = dp[i-1][0]+prices[i];
            dp[i][3] = dp[i-1][2];
        }
        return max(dp[len-1][1], max(dp[len-1][2], dp[len-1][3]));  // 最后一天一定不持股了，包含这三种情况
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

714 买卖股票的最佳时期含手续费

// dp[i][0] 持有股票 dp[i][1] 不持有股票
// dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0]);  // 当天买的还是之前买的
// dp[i][1] = max(dp[i-1][0]+prices[i]-fee, dp[i-1][1]); // 当天卖的还是之前卖的
// 初始化dp[0][0]=-prices[0]; dp[0][1] = 0;
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2,0));
        dp[0][0] = -prices[0];
        for(int i=1; i<len; i++){
            dp[i][0] = max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-1][0]+prices[i]-fee, dp[i-1][1]);
        }
        return dp[len-1][1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

子序列问题

子序列(不连续)

300 最长递增子序列

// dp[i] 以nums[i]结尾的最长递增子序列的长度
// dp[i] = max(dp[i], dp[j]+1); 如果nums[i]>nums[j]，dp[i]=dp[j]+1; 
// dp[i] = 1;
// 时间复杂度O(n²)， 空间复杂度O(n)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        for(int i=1; i<len; i++){
            for(int j=0; j<i; j++){
                if(nums[i]>nums[j])
                    dp[i] = max(dp[i], dp[j]+1);    // 这里是取dp[j]+14的最大值
            }
        }
        // return dp[len-1];   // 注意以最后一个元素结尾的可能不是最长的
        int result=0;
        for(int& i:dp)
            result = result>i? result:i;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1143 最长公共子序列

// dp[i][j]表示以text1[i-1]和text2[j-1]结尾的字符串的最长公共子序列
// if(text1[i-1] == text2[j-1]) dp[i][j] = max(dp[i-1][j-1])+1;
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));
        for(int i=1; i<=text1.size(); i++){
            for(int j=1; j<=text2.size(); j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1035 不相交的线

// 仔细想想这题和 最长公共子序列是一样的
// d[i][j]表示以nums1[i-1]和nums2[j-1]结尾的连成的做大线数
// if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
// else dp[i][j] = max(dp[i-1][j-1], max(dp[i][j-1]), dp[i-1][j]);
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1));
        for(int i=1; i<=nums1.size(); i++){
            for(int j=1; j<=nums2.size(); j++){
                if(nums1[i-1] == nums2[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i-1][j-1], max(dp[i][j-1], dp[i-1][j]));
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

子序列(连续)

674 最长连续递增序列

// dp[i] 以nums[i]结尾的最长连续递增序列
// if(nums[i]>nums[i-1]) dp[i] = dp[i-1]+1;
// 初始化：dp[i] = 1;
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        for(int i=1; i<len; i++){
            if(nums[i]>nums[i-1])
                dp[i] = dp[i-1]+1;
        }
        int result = 0;
        for(int& i:dp)
            result = result>i? result:i;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

718 最长重复子数组

// dp[i][j]：以nums1[i-1]和nums2[j-1]结尾的数组的最长重复子数组长度为dp[i][j]
// if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1; 否则归0，实际初始化就是0
// 时间复杂度：O(n × m)，n 为A长度，m为B长度
// 空间复杂度：O(n × m)
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
        int result = 0;
        for(int i=1; i<=nums1.size(); i++){
            for(int j=1; j<=nums2.size(); j++){
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j] = dp[i-1][j-1] +1;     // 这里i-1不能越界，所以定义成dp[i][j]对应nums1[i-1],nums2[j-1]
                result = result>dp[i][j]? result:dp[i][j];
            }
        }
        return result;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

53 最大子序和

// dp[i] 以nums[i]结尾的子数组和的最大值
// dp[i]有两种情况，延续前面的继续算dp[i-1]+nums[i]，前面的不要了，重新开始算nums[i]
// dp[i] = max(dp[i-1]+nums[i], nums[i]);
// 初始化：dp[0] = nums[0]>0? nums[0]:0;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];    // 这个题[-1]输出应该是-1， 本来想的dp[0] = max(nums[0], 0);
        int result = dp[0];
        for(int i=1; i<nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            result = result>dp[i]? result:dp[i];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

编辑距离

392 判断子序列

// 这题最优解肯定是双指针，但是也可以用动态规划解决
// 如果最长公共子序列长度等于s.size()，就说明s是t的子序列
// dp[i][j]表示以s[i-1], t[j-1]结尾的最长公共子序列长度
// if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+1;
// else dp[i][j] = dp[i][j-1];
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
        for(int i=1; i<= s.size(); i++){
            for(int j=1; j<=t.size(); j++){
                if(s[i-1] == t[j-1])
                    dp[i][j] = dp[i-1][j-1]+1;
                else
                    dp[i][j] = dp[i][j-1];  // t要删除元素，继续匹配
            }
        }
        return dp[s.size()][t.size()]==s.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

115 不同的子序列

// s有多少种删除元素的方式可以变成t
// dp[i][j]，以s[i-1]结尾的子序列中包含以t[j-1]结尾的个数为dp[i][j]
// if(s[i-1] == t[j-1]) dp[i][j]=dp[i-1][j-1](需要s[i-1]匹配) + dp[i-1][j](虽然相等，但是t[j-1]已经匹配了前面的)
// else dp[i][j] = dp[i-1][j]（s[i-1]匹配不上，所以删除）
// 初始化：dp[i][0] = 1; dp[0][j]=0;dp[0][0]=1; 初始化要带入递推公式验证

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size()+1, 0));   // 
        for(int i=0; i<=s.size(); i++)
            dp[i][0]=1;
        for(int i=1; i<=s.size(); i++){
            for(int j=1; j<=t.size(); j++){
                if(s[i-1]==t[j-1])
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

583 两个字符串的删除操作

// 找出最长公共子序列，然后把剩下的删除？
// dp[i][j] 以word1[i-1]和word2[j-1]结尾的公共子序列长度
// if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
// else dp[i][j] = max(dp[i][j-1], dp[i-1][j])  // 删除哪个元素？
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1));
        for(int i=1; i<=word1.size(); i++){
            for(int j=1; j<=word2.size(); j++){
                if(word1[i-1]==word2[j-1]) 
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
        }
        return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

72 编辑距离

// dp[i][j] 以word1[i-1]结尾和word2[j-1]结尾最少操作次数
// if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1]
// else min(dp[i][j-1]+1, dp[i-1][j]+1， dp[i-1][j-1]+1), 分别对应增、删改
// 注意增删是逆操作
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        // 初始化，因为递推公式需要用到第一行和第一列
        for(int i=0; i<=word1.size(); i++) dp[i][0]=i;  //有多少删多少
        for(int j=0; j<=word2.size(); j++) dp[0][j]=j;
        for(int i=1; i<=word1.size(); i++){
            for(int j=1; j<=word2.size(); j++){
                if(word1[i-1]==word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(min(dp[i][j-1],dp[i-1][j]), dp[i-1][j-1])+1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

647 回文子串

// dp[i][j], s[i]到s[j]范围内的子串是不是回文子串[i, j]
// if(s[i]==s[j]) if(i==j || j==i+1) dp[i][j]==true; else dp[i][j] = dp[i+1][j-1];
// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i; j<s.size(); j++){
                if(s[i]==s[j]){
                    if(j-i<=1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i+1][j-1];    // 要用到dp[i+1]，所以i是从后往前遍历, j是从前往后遍历
                }
                if(dp[i][j]==true) result++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

516 最长回文子序列

// dp[i][j] s[i]到s[j]的最长回文子序列
// if(s[i]==s[j]) if(j-i<=1) dp[i][j]=j-i+1; else dp[i][j]=dp[i+1][j-1]+2;
// else dp[i][j] = max(dp[i+1][j], dp[i][j-1])
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for(int i=s.size()-1; i>=0; i--){
            for(int j=i; j<s.size(); j++){    
                if(s[i]==s[j]){
                    if(j-i<=1)
                        dp[i][j] = j-i+1;
                    else
                        dp[i][j] = dp[i+1][j-1]+2;
                }
                else{
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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