1. Toy模板网首页
  2. > Toy博客

动态规划基础

8月前 作者：林深归海 分类：Toy博客 阅读(32) 违法举报

这篇具有很好参考价值的文章主要介绍了动态规划基础。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1. 解决动态规划的基本思路

一维dp例题

1. 爬楼梯（力扣70）

2. 整数划分问题

解题步骤：

3.非连续子数组和（该题与力扣198题打家劫舍相似）

解题步骤：

力扣198打家劫舍

4. 最大子数组和（力扣53）

分析：

代码：

二维dp例题

1. 01背包

代码：

2. 最长公共子序列（力扣1143）

代码：

3. 最长重复子数组（力扣718）

代码：

4. 编辑距离（力扣72）

代码

5. 完全背包

分析：

代码：

1. 解决动态规划的基本思路

动态规划：通过子问题的求解得到最终问题的答案

1. 定义问题：即定义dp数组。明确dp数组的含义

2. 分解问题：一般是根据题意得到递推式

3. 解决子问题：根据dp数组的定义求出边界条件，即dp数组的初始化操作

一维dp例题

1. 爬楼梯（力扣70）

1. 定义dp数组：
      dp[i]：为爬到i级的种类是dp[i]
    
2. 分解（向前递推:考虑最后一步如何决策）
       考虑最后一阶楼梯怎么爬（最后一步的决策）
             如爬到第6阶的种类可由第五阶向上爬一阶，也可以从第四阶爬两阶
             即 dp[i] = dp[i - 1] + dp[i - 2]
 
3. 解决子问题（不能继续分解的子问题）
                如此题中 dp[1] = 1 dp[2] = 2 

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return n;

        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;

        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
};

2. 整数划分问题

将一个整数用1，3，4进行划分，问有多少种情况？
例如：5 = 1 + 1  + 1 + 1 + 1
                            = 1 + 1 + 3
                            = 1 + 3 + 1
                            = 3 + 1 + 1
                            = 4 + 1
                            = 1 + 4 共六种

解题步骤：

1. 定义dp数组：
      dp[i]：将i划分，共有dp[i]种
    
2. 分解（向前递推:考虑最后一步如何决策）
**考虑最后一个数字选 1，3还是 4**（最后一步的决策）
            i可分解为 x1 + x2 + x3 + …… + xk
            如果xk = 1， 则 dp[i] = dp[i -1]
            如果xk = 3， 则 dp[i] = dp[i -3]
            如果xk = 4， 则 dp[i] = dp[i -4]
            得：dp[i] = dp[i -1] + dp[i -3] + dp[i -4]。一定要明确dp数组的含义
 
3. 解决子问题（不能继续分解的子问题）
                如此题中 dp[1] = 1 dp[2] = 1 dp[3] = 2 dp[4] =  4

3.非连续子数组和（该题与力扣198题打家劫舍相似）

eg：a[] = {3 5 7 6  2 4} 求最大子数组和（禁用相邻元素）
选3不选5，选5不选3和7。以此类推

解题步骤：

1. 定义dp数组：
    dp[i]为 [a[0], a[i]] 区间内的最大子数组和。如上例中便是求 d[5]
    
    
2. 分解（向前递推:考虑最后一步如何决策）
        **考虑最后一个元素a[i]用还是不用**（最后一步的决策）
            1. 不用最后一个元素a[i]：dp[i] = dp[i -1];
            2. 用最后一个元素a[i]：dp[i] = dp[i -2] + a[i]；
故递推方程为：dp[i] = max(d[i -1], dp[i -2] + a[i]);            

3. 子问题
dp[0] = max(0, a[0]);
dp[1] = max(a[1], dp[0]);

力扣198打家劫舍

1. 定义问题：
      dp[i] 表示前 i 间房屋能偷窃到的最高总金额
        最终目标：求dp[len]
2. 分解问题（向前递推:考虑最后一步如何决策）
      考虑第i家偷不偷（最后一步的决策）
        1.如果偷第i家： dp[i] = dp[i -2] + a[i -1]
        2.如果不偷第i家：dp[i] = dp[i -1]
故递推方程为：dp[i] = max(dp[i-1], dp[i -2] + a[i -1])
3. 解决子问题（根据dp数组的定义）
            dp[0] = 0
            dp[1] = a[0]

class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();

        vector<int> dp(len +1, 0);
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= len; i++){
            dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
        }

        return dp[len];
    }
};

4. 最大子数组和（力扣53）

该题与第三题的区别：第三题是有后效性的，该题是没有后效性的。

当你对第三题的问题进行分解时，第一个子问题的答案一般与第二个子问题的答案有明显的联系。只要知道递推式，然后求得dp数组的最终结果就能得到答案。而对于该题这种无后效性的问题，一般求解的是dp数组的max值。后面二维dp中也有类似的题目

分析：

1. 定义问题
dp[i]：以a[i]结尾的 [a[0], a[i]] 区间内最大子数组的和为 dp[i]

2. 分解问题
因为必须以a[i]结尾，故可得递推方程 dp[i] = dp[i -1] + a[i]。
考虑 dp[i -1]的符号及其定义，有以下两种情况发生
1. 当dp[i - 1] <=0 时，递推方程为：dp[i] = a[i]
2. 当dp[i -1] > 0 时，递推方程为：dp[i] = dp[i -1] + a[i];
3. 因为求的是最大连续子数组和，所以最后取值为 max(所有的dp[i][j]) 。dp数组中的最大值

3. 解决子问题
dp[0] = a[0]

代码：
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        
        vector<int> dp(len, 0);
        dp[0] = nums[0];

        int max = dp[0];
        for(int i = 1; i < len; i++){
            if(dp[i -1] < 0){
                dp[i] = nums[i];
            }else{
                dp[i] = dp[i -1]+ nums[i];
            }
            if(dp[i] > max) max = dp[i];
        }

        return max;
    }
};

二维dp例题

1. 01背包

  • 01背包：n种物品，每个物品只有一个，放入一个容量为C的背包，求最大价值
  • 完全背包：n种物品，每个物品有无限个，放入一个容量为C的背包，求最大价值
  • 多重背包：n种物品，每个物品个数各不相同，放入一个容量为C的背包，求最大价值

1. 定义dp数组：
      dp[i][j]：前 i 件商品，放入容量为 j 的背包 的最大价值为 dp[i][j]
      eg：求解dp[4][8]  //将前4件商品，放入容量为8的背包所得最大价值为 dp[4][8]
2. 分解（向前递推:考虑最后一步如何决策）
     i件商品： [0][1][2]……[i-2][i-1]
考虑第 i 件商品 是否放入背包（最后一步的决策）
eg:
    dp[4][8] = max(dp[3][8], 6 + dp[3][3])  // 第4件商品的价值为6，容量为5
    将前 4 件商品放入容量为8的背包最大价值：
        1. 第四件商品不放入，即前三件商品放入容量为8的背包的最大价值
        2. 第四件商品放入，将前三件商品放入容量为 3 的背包
                                                的最大价值 + 第四件商品的价值
                                                
得递推方程 dp[i][j] =     max(dp[i - 1][j],  v[i -1] + dp[i-1][j - w[i -1])


3. 解决子问题（不能继续分解的子问题）
    dp[0][0] = 0  0物品放入0容量背包
    dp[i][0] = 0  前i件物品放入容量为0背包
    dp[0][j] = 0  0物品放入容量为i的背包

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

int M, N; //M:物品种类，N:背包容量

void solve(){
    vector<int> weight(M, 0); //每件物品所占空间
    vector<int> value(M, 0);  //每件物品的价值
    
    //每件物品的价值，所占空间 初始化
    for(int i = 0; i < M; i++) cin >> weight[i];
    for(int i = 0; i < M; i++) cin >> value[i];
    
    //二维dp数组的定义:
    //    dp[i][j]：前i件物品，放入容量为j的背包，所得到的最大价值为dp[i][j]
    vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
  
    //这里初始化可以省略，因为在定义dp数组时所有的元素都是0
    //for(int i = 0; i <= M; i++) dp[i][0] = 0;
    //for(int j = 0; j <= N; j++) dp[0][j] = 0;
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            if(weight[i -1] > j){ //第i件物品所占空间比背包空间还大，则第i件物品不放入背包
                dp[i][j] = dp[i -1][j];
            }else{
                dp[i][j] = max(dp[i -1][j], value[i -1] + dp[i -1][j - weight[i -1]]);
            }
        }
    }
    
    cout << dp[M][N] << endl;
}

int main(){
    cin >> M >> N;
    solve();
    
    return 0;
}

2. 最长公共子序列（力扣1143）

跟一维dp中的第3题类似

1. 定义dp数组
            dp[i][j] ：s1前i个字符与s2前j个字符的最长公共子序列长度为 dp[i][j].
            最终目标：dp[m][n]
            
2. 分解问题（向前递推:考虑最后一步如何决策）
**考虑s1中第i个元素是否与s2中第j个元素相同**（最后一步的决策）
1. 如果相同，即 s1[i -1] == s2[j -1], 则 dp[i][j] = dp[i -1][j -1] + 1
2. 如果不相同，则考虑 s1 的前 i -1 个字母 和 s2 的 前 j个字母比较，以及 s1 的前 i 个字母和s2的前j -1个字母比较，取其中的较大者。 即 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
3. 子问题（根据dp数组的定义）
            dp[0][0] = 0 
            dp[i][0] = 0
            dp[0][j] = 0

代码：
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();

        vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; 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[m][n];
    }
};

3. 最长重复子数组（力扣718）

该问题同一维dp中的第4题相似，是一个无后效性问题，需求dp数组的max值

1. 定义问题
dp[i][j]：nums1中以i结尾的前i项 和 nums2中以j结尾的前j项 最长连续公共子数组的长度为dp[i][j]

2. 分解问题
**考虑nums1中第i个元素是否与nums2中第j个元素相同**
1. 相同，则不难推出 dp[i][j] = dp[i -1][j -1] + 1
2. 不同，dp[i][j] = 0【求的是 nums1中以i结尾的前i项 和 nums2中以j结尾的前j项最长相等后缀，但后缀的第一个元素就不相等】
3. 因为求的是最长相等后缀，所以最后取值为 max(所有的dp[i][j]) 。dp数组中的最大值

3. 解决子问题
dp[0][0] = 0
dp[i][0] = 0
dp[0][j] = 0

代码：
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
        int max = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i -1] == nums2[j -1]){
                    dp[i][j] = dp[i -1][j -1] + 1;
                }
                if(dp[i][j] > max) max = dp[i][j];
            }
        }

        return max;
    }
};

4. 编辑距离（力扣72）

1. 定义dp数组
            dp[i][j]：s1前i个字符转化为s2的前j个字符需要的最少的操作数为dp[i][j]， 如将 sun 转换成satur需要最少3次操作，故 dp[3][5] = 3。最终目标是求：dp[m][n]

2. 分解问题
                1. s1 和 s2 末尾字符相同，则无需考虑最后一个字符的转换。
                        即当 s1[i -1] == s2[j -1]时， dp[i][j] = dp[i -1][j -1]
                2. s1 和 s2 末尾字符不相同时，对s1进行插入，删除，替换操作
                 （题意是将s1转换为s2，所以下面所有操作都是对s1进行操作）
                         1.若进行插入操作，即s1[i] = s2[j -1] 则默认 s1前 i 项 与 s2 前 j -1                  项高度重合。dp[i][j] = dp[i][j -1] + 1
                         2.若进行删除操作，即s1[i -1] = NULL, 则默认 s1前 i -1项与 s2前
                              j 项高度重合。dp[i][j] = dp[i-1][j]  + 1
                       3. 若进行替换操作，即 s1[i-1] = s2[j -1], 则默认 s1前i -1项 与s2
                           前 j -1项高度重合。dp[i][j] = dp[i-1][j-1] + 1

故dp[i][j] = min( dp[i][j -1] + 1, dp[i-1][j]  + 1, dp[i-1][j-1] + 1);

3. 解决子问题
        通过dp数组定义来确定子问题的解
             dp[0][0] = 0;
             dp[i][0] = i;  // 将s1 的前i个字符转换为s2 的前0个字符。即将s1的前i个字符删除
             dp[0][j] = j;  //将s1插入j次得到s2

代码
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        vector<vector<int>> dp(m +1, vector<int>(n +1, 0));
        for(int i = 0; i <= m ; i++) dp[i][0] = i;
        for(int j = 0; j <= n; j++) dp[0][j] = j;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1[i -1] == word2[j -1]){ // w1的第i个字符和w2的第j个字符相同
                    dp[i][j] = dp[i -1][j -1];
                }else{
                    dp[i][j] = min(min(dp[i -1][j] +1, dp[i][j -1] +1), dp[i -1][j -1] +1);
                }
            }
        }
        
        return dp[m][n];
    }
};

5. 完全背包

n种物品，每个物品有无限个，放入一个容量为C的背包，求最大价值。

完全背包是基于01背包扩展而来。可以看完01背包再来看这个。

完全背包和01背包最大的区别就是完全背包可以放入多件同种物品。表现在dp数组中有如下区别，详细讲解见下面的分析：

01背包：dp[i][j] =     max(dp[i - 1][j],  v[i -1] + dp[i-1][j - w[i -1])

完全背包：dp[i][j] =     max(dp[i - 1][j],  v[i -1] + dp[i][j - w[i -1])

分析：

1. 定义dp数组：
      dp[i][j]：前 i 件商品，放入容量为 j 的背包 的最大价值为 dp[i][j]
      eg：求解dp[4][16]


2. 分解（向前递推:考虑最后一步如何决策）

eg:
    dp[4][16] = max(dp[3][16], 6 + dp[4][11])  // 第4件商品的价值为6，容量为5
    将前 4 件商品放入容量为16的背包最大价值：
        1. 第四件商品不放入，即前三件商品放入容量为16的背包的最大价值
        2. 第四件商品放入，如果背包中剩余的空间还能放入第四件商品，继续将前四件商品放入容量为 11 的背包的最大价值 + 第四件商品的价值

  i件商品： [0][1][2]……[i-2][i-1]

考虑第 i 件商品 是否放入背包（最后一步的决策）

  1. 第i件物品不放入，则 dp[i][j] = dp[i -1][j]
  2. 第i件物品放入，由于该物品有无限个，考虑背包剩余的空间能否继续放第i件物品，如果能继续放第i件物品，则 dp[i][j] = dp[i][j -w[i -1]] + v[i -1] 

注：对于第二步，本质还是将其当成01背包去处理，每次只放一件物品

得递推方程 dp[i][j] =     max(dp[i - 1][j],  v[i -1] + dp[i][j - w[i -1]])


3. 解决子问题（不能继续分解的子问题）
    dp[0][0] = 0  0物品放入0容量背包
    dp[i][0] = 0  前i件物品放入容量为0背包
    dp[0][j] = 0  0物品放入容量为i的背包

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

int M, N; //M:物品种类，N:背包容量

void solve(){
    vector<int> weight(M, 0); //每件物品所占空间
    vector<int> value(M, 0);  //每件物品的价值
    
    //每件物品的价值，所占空间 初始化
    for(int i = 0; i < M; i++) cin >> weight[i] >> value[i];
    
    //二维dp数组的定义:
    //    dp[i][j]：前i件物品，放入容量为j的背包，所得到的最大价值为dp[i][j]
    vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
  
    //这里初始化可以省略，因为在定义dp数组时所有的元素都是0
    //for(int i = 0; i <= M; i++) dp[i][0] = 0;
    //for(int j = 0; j <= N; j++) dp[0][j] = 0;
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            if(weight[i -1] > j){ //第i件物品所占空间比背包空间还大，则第i件物品不放入背包
                dp[i][j] = dp[i -1][j];
            }else{
                dp[i][j] = max(dp[i -1][j], value[i -1] + dp[i][j - weight[i -1]]);
            }
        }
    }
    
    cout << dp[M][N] << endl;
}

int main(){
    cin >> M >> N;
    solve();
    
    return 0;
}

6. 多重背包

n种物品，每个物品个数各不相同，放入一个容量为C的背包，求最大价值

例：

有M种物品和一个容量为C 的背包。第i种物品最多有Mi件，每件耗费的空间是Wi ，价值是Vi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

同完全背包，本质是将其转为01背包。

故需要添加一个数组count记录每件物品的个数，当添加第i个物品时，第i个物品的取值范围是[1, Mi]，从其中找一个符合条件的最大值k，表示前k件第i个物品能放进背包的剩余空间，而第 k+1件第i个物品不能放进背包的剩余空间文章来源地址https://www.toymoban.com/news/detail-751899.html

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

int M, N; //M:物品种类，N:背包容量

void solve(){
    vector<int> weight(M, 0); //每件物品所占空间
    vector<int> value(M, 0);  //每件物品的价值
    vector<int> count(M, 0); // 每件物品的个数
    
    //每件物品的 所占空间，价值，个数 初始化
    for(int i = 0; i < M; i++) cin >> weight[i];
    for(int i = 0; i < M; i++) cin >> value[i];
    for(int i = 0; i < M; i++) cin >> count[i];

    
    //二维dp数组的定义:
    // dp[i][j]：前i件物品，放入容量为j的背包，所得到的最大价值为dp[i][j]
    vector<vector<int>> dp(M+1, vector<int>(N+1, 0));
  
    //这里初始化可以省略，因为在定义dp数组时所有的元素都是0
    //for(int i = 0; i <= M; i++) dp[i][0] = 0;
    //for(int j = 0; j <= N; j++) dp[0][j] = 0;
    
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            dp[i][j] = dp[i -1][j];  // 不放第i个物品
            // 放k件第i个物品；直到k件第i个物品所占空间大于背包剩余容量，则不再继续放第 k+1件第i个物品
            for(int k = 1; k <= count[i -1] && k * weight[i -1] <= j; k++){
                dp[i][j] = max(dp[i][j], k * value[i -1] + dp[i -1][j - k * weight[i -1]]);
            }
        }
    }
    
    cout << dp[M][N] << endl;
}

int main(){
    cin >> N >> M;
    solve();
    
    return 0;
}

到了这里，关于动态规划基础的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • OJ刷题---[算法课动态规划]走网格（C++完整代码）

    OJ刷题---[算法课动态规划]走网格（C++完整代码）

    m行n列的网格，从左上角（1，1）出发，每一步只能向下或者向右，问共有多少种方法可以走到右下角（m,n); 输入参数 m n (1=m=10 1=n=10) 输出多少种走法 比如： 输入：2 3 输出：3 输入：5 5 输出：70 完整代码（C++）： 结果： 注意：最后调用的时候，是调用sum(m,n)，而不是sum(m+1

    2024年02月07日
    浏览(31)

  • 【leetcode刷题之路】剑指Offer（4）——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右，中序遍历是左根右，这也就意味着前序遍历的第一个节点是整棵树的根节点，顺着这个节点找到它在中序遍历中的位置，即为in_root，那么in_root左边的都在左子

    2024年02月11日
    浏览(43)

  • 【leetcode刷题之路】初级算法（2）——链表+树+排序和搜索+动态规划

    3.1 【链表】删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/ 给出的就是要删除的那个节点，直接前后移动就行了。 3.2 【双指针】删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/ 利用双指针left和right，首先让right遍历n个节点，再让两

    2024年02月10日
    浏览(38)

  • 力扣算法刷题Day39｜动态规划：不同路径 I&II

    力扣题目：#62.不同路径 刷题时长：参考题解后10min 解题方法：动规 复杂度分析 时间O(m*n) 空间O(m*n) 问题总结 初始化二维数组的python语法：i 对应 m，j 对应n 二维遍历顺序，从上到下从左到右通过两层for循环实现，其中startindex应为1 本题收获 动规思路 确定dp数组及下标的含义

    2024年02月12日
    浏览(46)
  • 【算法日志】动态规划刷题：01背包问题，多重背包问题(day37,day38)

    【算法日志】动态规划刷题：01背包问题，多重背包问题(day37,day38)

    目录 前言 目标和（01背包） 一和零（01背包） 零钱兑换（多重背包） 排列总和（多重背包） 这两天都是背包问题，其中的01背包的一些应用问题需要一定的数学建模能力，需要i将实际问题简化成我们熟悉的背包问题；而这两天的多重背包问题还算比较基础，但也要我明白了

    2024年02月11日
    浏览(37)

  • 力扣算法刷题Day42｜动态规划：01背包问题 分割等和子集

    力扣题目：01背包问题（二维数组） 刷题时长：参考题解 解题方法：动态规划 + 二维dp数组 复杂度分析 时间 空间 问题总结 理解递推公式困难 本题收获 动规思路：两层for循环，第一层i遍历物品，第二层j枚举背包容量以内所有值 确定dp数组及下标的含义：dp[i][j] 表示从下标

    2024年02月13日
    浏览(42)

  • 力扣算法刷题Day44｜动态规划：完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目：#518.零钱兑换II（完全背包组合问题） 刷题时长：7min 解题方法：动态规划（完全背包） 复杂度分析 时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换：纯完全背包是凑成背包最大价值是多少，而本

    2024年02月13日
    浏览(31)
  • 知识储备--基础算法篇-动态规划

    知识储备--基础算法篇-动态规划

    第一次接触动态规划，不知道具体什么意思，做了题才发现动态规划就是把大问题变成小问题，并解决了小问题重复计算的方法称为动态规划。比如上楼梯，一次上一阶或二阶，求有多少种算法，就可以拆成最后一阶的方法数等于前一阶的方法数加前两阶的方法数，这就是递

    2024年02月11日
    浏览(32)
  • 算法基础课第五讲 动态规划

    算法基础课第五讲 动态规划

    时间复杂度：状态数量 转移的计算量 * 总体概述：给一堆物品，有体积有价值。有一个背包，在背包能装下的前提下最终能装下多少（背包不一定要装满） DP问题：一般需要从两方面考虑：状态表示以及状态计算 状态表示：f(i,j) 从两个方面考虑：集合（所有选法的集合）（

    2024年02月01日
    浏览(31)
  • 基础算法之——【动态规划之路径问题】1

    基础算法之——【动态规划之路径问题】1

    今天更新动态规划路径问题1，后续会继续更新其他有关动态规划的问题！动态规划的路径问题，顾名思义，就是和路径相关的问题。当然，我们是从最简单的找路径开始！ 动态规划的使用方法： 1.确定状态并定义状态数组：（i，j）代表什么意思？dp[i][j]又是什么意思？ 2.确

    2024年02月07日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包