代码随想录算法训练营第38-57天 |第九章 动态规划13完成

动态规划五部曲

1. dp数组以及下标的定义
2. 递推公式
3. dp数组如何初始化的
4. 遍历顺序
5. 打印dp数组

动态规划01

• 509. 斐波那契数
• 70. 爬楼梯
• 746. 使用最小花费爬楼梯

509. 斐波那契数

//递归做法
class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        else if(n==1)
            return 1;
        else{
            return fib(n-1)+fib(n-2);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

//动态规划做法
class Solution {
public:
    int fib(int n) {
        if (n <= 1) return n;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            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

70. 爬楼梯

1. dp数组以及下标的定义： dp[i] 爬到第i层楼梯，有dp[i]种方法
2. 递推公式：爬到i层有两种方法，i-1层的时候跨一步，i-2层的时候跨两步。（不能拆开思考i-2层跨两步，因为如果是i-2层跨一步后再跨一步，其实就是i-1层跨一步来的了。）所以递推公式为d[i]=d[i-1]+d[i-2]
3. dp数组如何初始化的：dp[1]=1 dp[2]=2 （我的思路是，按照递推公式反推dp[0]=1）
4. 遍历顺序 for(i=3;i<=n;i++)
5. 打印dp数组

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+2);
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];

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

错误以及注意事项

• 0-n 总共有n+1个元素，为了防止越界，我们初始化为n+2个大小。

746. 使用最小花费爬楼梯

1. dp数组以及下标的定义： dp[i] 到达下标i时所需要的花费
2. 递推公式：爬到i层有两种方法，i-1层的时候跨一步，i-2层的时候跨两步。dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
3. dp数组如何初始化的：dp[0]=0 dp[1]=0 （初始可以任意选择0，1开始爬坡）
4. 遍历顺序 for(int i=2;i<=cost.size();i++)
5. 打印dp数组

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

错误以及注意事项

• 初始可以选择0，1出发，所以dp[0],dp[1]都是0。
• 越过最后一个元素上了楼顶才是题目要的答案，所以最后返回的是cost.size()处的答案，新建dp数组的时候是cost.size()+1。

动态规划02

• 62.不同路径
• 63. 不同路径 II

62.不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 0;
        for(int i=1;i<n;i++) dp[0][i]=1;
        for(int i=1;i<m;i++) dp[i][0]=1;
        for (int i = 1; i <= m - 1; i++) {
            for (int j = 1; j <= n - 1; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        // 打印 dp 数组
        cout << "DP Array:" << endl;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }

        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

错误以及注意事项

• 初始化，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。

63. 不同路径 II

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

错误以及注意事项

• 在初始化的时候要注意，最边上两条xy轴，只要遇到了障碍，后面的都无法通行，就会变成0。

动态规划03

• 343. 整数拆分
• 96.不同的二叉搜索树

343. 整数拆分

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

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

错误以及注意事项

• dp[i]=max(dp[i], max((i - j) * j, dp[i - j] * j)); 注意这里是三个数之间的最大值，不是拆的越多越大，所以！

96.不同的二叉搜索树

1. dp数组以及下标的定义： 输入i，有dp[i]种不同的二叉树
2. 递推公式：因为是二叉搜索树，所以根节点的值决定了左右子树各有多少节点dp[3] = 头1+头2+头3=（左0右2+左1右1+左2*右0）
3. dp数组如何初始化的：dp[0]=1 dp[1]=1 （初始可以任意选择0，1开始爬坡）
4. 遍历顺序 for(int i=3;i<=n;i++)
5. 打印dp数组

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+2,0);
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        // dp[3] = 头1+头2+头3=（左0*右2+左1*右1+左2*右0）
        for(int i=3;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
19

动态规划04

• 01背包问题，你该了解这些！
• 01背包问题，你该了解这些！ 滚动数组
• 416. 分割等和子集

416. 分割等和子集

我怎么看不懂这个呢！！

动态规划05

• 1049. 最后一块石头的重量 II
• 494. 目标和
• 474.一和零

1049. 最后一块石头的重量 II

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：

组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

⭐️ 相当于尽量将石头分配为重量相近的两堆——sum为复数且两堆重量相等，则最后不剩下来石头了。这个是01背包问题！
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

循环注意事项：
先循环石头，再倒序循环背包（因为一个物品只能装一次）。j>stones[i]的条件一是因为在装入的时候要确认背包容量还够用，（通过dp[j-stones[i]]不能越界来记住条件要求！）

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i=0;i<stones.size();i++){
            sum+=stones[i];
        }
        int halfsum = sum / 2;
        vector<int> dp(halfsum+1,0);
        for(int i=0;i<stones.size();i++){ //stone
            for(int j = halfsum;j>=stones[i];j--) //背包
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        if(dp[halfsum]*2 ==sum)
            return 0;
        else
            return sum-2*dp[halfsum];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

494.目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5

⭐️ 这里需要分成两半数据，一半是正数，剩下的一半是负数。假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target x = (target + sum) / 2
⭐️ 不论是回溯法暴力求解还是使用动态规划背包问题的思想来做，目标值都是这个求到的x，放和为多少的正数放进path。

动态规划：
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

⭐️⭐️求组合类问题的公式

dp[j] += dp[j - nums[i]]
1

class Solution {
public:
	//1. 回溯法
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int cursum, int targetSum, int startIndex){
        if(cursum == targetSum){
            result.push_back(path); //不能写return 这个需要递归到最后的深度
        }
        if(cursum>targetSum) return;
        for(int i =startIndex;i<nums.size();i++)
        {
            cursum+=nums[i];
            path.push_back(nums[i]);
            backtracking(nums,cursum,targetSum,i+1);
            path.pop_back();
            cursum-=nums[i];
        }
        

    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
        }
        if((target+sum) % 2 != 0) return 0; //如果不能整除则不可能实现。
        if(abs(target)>sum) return 0;
        int targetSum = (target+sum)/2;
        
        // int startIndex = 0;
        // int cursum=0;
        // backtracking(nums,cursum,targetSum,startIndex);
        // return result.size();


        //2. dp动态规划方法
        vector<int> dp(targetSum+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++)
            for(int j = targetSum;j>=nums[i];j--)
            {
                dp[j] += dp[j-nums[i]];
            }
        return dp[targetSum];
        
    }
};
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

dp变化图

错误以及注意事项

• 回溯法做的时候注意这一题是要遍历完全，到最深的部分，不能提前返回，所以终止条件中没有return
• 动态回归的方法把二位动态方程再学学。
• 因为不能重复放所以，第一个循环遍历物品，第二个循环倒序遍历背包。

474.一和零

1. dp数组以及下标的定义 dp[i][j] 装进i个0和j个1的子集大小为dp[i][j]
2. 递推公式，dp[i][j]能由减去上一个元素中的0，1个数推出。dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1); //dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1
3. 如何初始化，01背包的dp数组初始化为0就可以。
4. 遍历顺序，先遍历物品然后倒序遍历背包
5. 打印dp数组

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 zeroNum = 0;
            int oneNum = 0;
            for(char c : str){
                if(c=='0')
                    zeroNum++;
                else
                    oneNum++;
            }
            for(int i = m;i>=zeroNum;i--)
                for(int j = n;j>=oneNum;j--)
                    dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
        }
        // for(int i=0;i<=m;i++){
        //     for(int j=0;j<=n;j++)
        //         cout<<dp[i][j]<<' ';
        //     cout<<endl;
        //     }
        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

这一题可以用来区分多个背包问题 待看！！

动态规划part06

• 完全背包
• 518.零钱兑换 II
• 377. 组合总和 Ⅳ

完全背包

卡码网52题

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

using namespace std;

int maxValue(vector<int> weight, vector<int> value, int bagsize){
    // int nums = weight.size();
    vector<int> dp(bagsize+1,0);
    for(int i =0;i<weight.size();i++)
        for(int j=weight[i];j<=bagsize;j++)
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
    return dp[bagsize];
}


int main(){
    int N,V;
    cin>>N>>V;
    vector<int> weight(N,0);
    vector<int> value(N,0);
    for(int i=0;i<N;i++){
        int w;
        int v;
        cin >> w >>v;
        weight[i]=w;
        value[i]=v;
    }
    int result = maxValue(weight,value,V);
    cout<<result<<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

错误以及注意事项

• 完全背包和01背包的区别就在于物品能否重复放，01不能所以背包是倒序遍历，完全背包可以所以for(int j=weight[i];j<=bagsize;j++) 这里条件不要搞错了。
• 自定义输入输出的写法不熟练。

518.零钱兑换 II

class Solution {
public:
    //dp[j] 总金额j可有dp[j]中方式凑出。coins可以重复使用，完全背包问题
    //求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0]=1; //背包容量为0的时候只有一种方法。
        for(int i = 0;i< coins.size();i++)
            for(int j=coins[i];j<=amount;j++)
            {
                dp[j] += dp[j - coins[i]];
            }
        for(int i =0;i<amount+1;i++)
            cout<< dp[i]<<" ";
        return dp[amount];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

错误以及注意事项

• 这里要装满背包！注意递推公式。
• 小心初始化，如果dp[0]为0的话，后面所有的dp都无法更新。
• 如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。 这里是求组合数！

377. 组合总和 Ⅳ

class Solution {
public:
    long 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

错误以及注意事项

• ❓ 为什么有这一步？dp[j] < INT_MAX - dp[j - nums[i]]
• 因为是排列，所以先遍历背包，后遍历物品且可以多次重复放，所以背包是顺。

动态规划07

• 70. 爬楼梯 （进阶）
• 322. 零钱兑换
• 279.完全平方数

70. 爬楼梯 （进阶）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 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;
    // dp[1]=1;
    for(int j=0;j<=n;j++)
        for(int i=1;i<=m;i++){
            if(j>=i)
                dp[j]+=dp[j-i];
        }
    cout<<dp[n]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

错误以及注意事项

• n是背包容量，m是物品
• 可多次选物品——完全背包
• 排列问题 先遍历背包，再遍历物品。

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
而本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //最少的硬币个数，贪心，对coins进行降序排列。
        // sort(coins,false);
        //完全背包，先遍历背包，再遍历物品。
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int j=0;j<=amount;j++)
            for(int i=0;i<coins.size();i++)
            {
                if(j>=coins[i] &&  dp[j - coins[i]] != INT_MAX)
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }

        if(dp[amount]==INT_MAX)
            return -1;
        else
            return dp[amount];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

错误以及注意事项

• dp[j - coins[i]] != INT_MAX 是要保证前一步是可达的。

279.完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        dp[1]=1;
        for(int j=0;j<=n;j++)
            for(int i=1;i<=sqrt(n);i++){
                if(j>=i*i && dp[j-i*i]!=INT_MAX)
                    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

AC~

动态规划08

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1,false);
        dp[0] = true;
        for(int j = 0;j<=s.size();j++)
            for(int i = 0;i<j;i++)
            {
                string word = s.substr(i, j - i); //substr(起始位置，截取的个数)
                for(int z = 0; z< wordDict.size();z++)
                    if(word == wordDict[z] && dp[i]==true)
                        dp[j]=true;        
            }成分
        return dp[s.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16