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

【蓝桥杯C/C++】专题六：动态规划

9月前 作者：不会喷火的小火龙 分类：Toy博客 阅读(44) 违法举报

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

专题六：动态规划

在这里插入图片描述

导读

本专题将讲解最难理解的算法之一：动态规划。介绍动态规划的基本概念、算法原理以及应用场景。首先，我们将介绍动态规划的定义和特点，以及它与递归、贪心算法的区别。接着，我们将详细介绍动态规划的解题思路和算法流程，包括状态转移方程、边界条件、初始化等概念。最后，我们将讨论动态规划在实际问题中的应用，包括背包问题、最长公共子序列问题、最短路径问题等。

什么是动态规划

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题于最优子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的.

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

解决的问题

动态规划是一种数学方法，用于求解决策过程的最优化问题。如果一个问题可以分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑使用动态规划来解决这个问题。应用动态规划之前要分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解。如果将小问题的最优解组合起来能够得到整个问题的最优解，那么就可以使用动态规划解决问题。可以应用动态规划求解的问题主要具有以下四个特点：

  • 问题是求最优解。
  • 整体问题的最优解依赖于各个子问题的最优解。
  • 大问题分解成若干小问题，这些小问题之间还有相互重叠的更小的子问题。
  • 从上往下分析问题，从下往上求解问题。

解题步骤

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

分享两张两种解决动态规划的思维导图：

【蓝桥杯C/C++】专题六：动态规划

【蓝桥杯C/C++】专题六：动态规划

动态规划应该如何debug

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！

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

然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

记忆化搜索

可以理解为实现dp的另一种方法，用递归实现本质还是搜索。

记忆化搜索按照自顶向下的顺序，每求得一个状态时，就把它的解保存下来，以后再次遇到这个状态时就不用重复求解了。

记忆化搜索包含两个要素记忆化和搜索。

  • 沿用搜索的一般模式，本质还是用递归函数实现。
  • 在搜索的过程中将已经得到的解保存起来，下次需要时直接用。

斐波那契数

题目

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入： n = 2
输出： 1
解释： F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入： n = 3
输出： 2
解释： F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入： n = 4
输出： 3
解释： F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

代码

class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
       vector<int> dp(n+1);
       dp[0]=0;
       dp[1]=1;
       for(int i=2;i<=n;i++)
       {
           dp[i]=dp[i-1]+dp[i-2];
        //    cout<<dp[i]<<endl;
       }
       return dp[n];

    }
};

题解

动态规划五部曲：

  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. 确定遍历顺序

    从前往后循环遍历，dp问题一般都是自底向上去思考。

爬楼梯

题目

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入： n = 2

输出： 2

解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2：

输入： n = 3

输出： 3

解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

代码


class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

题解

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

  1. 确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

2 . 确定递推公式

如果可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

使用最小花费爬楼梯

题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入： cost = [10,15,20]

输出： 15

解释： 你将从下标为 1 的台阶开始。

  • 支付 15 ，向上爬两个台阶，到达楼梯顶部。

总花费为 15 。

示例 2：

输入： cost = [1,100,1,1,1,100,1,1,100,1]

输出： 6

解释： 你将从下标为 0 的台阶开始。

  • 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  • 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  • 支付 1 ，向上爬一个台阶，到达楼梯顶部。

总花费为 6 。

提示：

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

代码

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 <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

题解

  1. 确定dp数组以及下标的含义

使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。

对于dp数组的定义，大家一定要清晰！

  1. 确定递推公式

可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？

一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  1. dp数组如何初始化

看一下递归公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0] dp[1]推出。

  1. 确定遍历顺序

最后一步，递归公式有了，初始化有了，如何遍历呢？

本题的遍历顺序其实比较简单，简单到很多同学都忽略了思考这一步直接就把代码写出来了。

因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。

不同路径

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：
【蓝桥杯C/C++】专题六：动态规划

输入： m = 3, n = 7
输出： 28

示例 2：

输入： m = 3, n = 2

输出： 3

解释：

从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

示例 3：

输入： m = 7, n = 3
输出： 28

示例 4：

输入： m = 3, n = 3
输出： 6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

题解

dfs

注意题目中说机器人每次只能向下或者向右移动一步，那么其实

机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！

此时问题就可以转化为求二叉树叶子节点的个数

【蓝桥杯C/C++】专题六：动态规划

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

dp

  1. dp数组的定义

    dp[i][j]：表示从(0,0)出发到（i,j）的不同路径

  2. 确定递推顺序

    每个位置只有两个方向能走到，dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

  3. 数组初始化

    从（0,0）到（i,0）的位置一定只有一种，到（0，j）也同理

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

  4. 确定遍历顺序

    从上方和左边推导过来，只要从左往右一层一层遍历即可。

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 j = 0; j < n; j++) dp[0][j] = 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];
    }
};

凑硬币

题目

【蓝桥杯C/C++】专题六：动态规划

题解

dfs

#include<bits/stdc++.h>
using namespace std;
/*
coins：硬币的面额列表；
amount：需要凑的金额；
count：当前使用硬币的数量；
index：当前搜索的硬币面额的下标；
res：存储最少的硬币数量。
*/
void dfs(vector<int>& coins, int amount, int count, int index, int& res) {
    if (amount == 0) {
        res = min(res, count);
        return;
    }
    if (index == coins.size()) {
        return;
    }
    for (int k = amount / coins[index]; k >= 0 && count + k < res; k--) {
        dfs(coins, amount - k * coins[index], count + k, index + 1, res);
    }
}

int coinChange(vector<int>& coins, int amount) {
    sort(coins.rbegin(), coins.rend());
    int res = INT_MAX;
    dfs(coins, amount, 0, 0, res);
    return (res == INT_MAX ? -1 : res);
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount;
    cin>>amount;
    int res = coinChange(coins, amount);
    cout << res << endl;
    return 0;
}

dp

#include<bits/stdc++.h>
using namespace std;
int amount;
vector<int> coins={1,2,5};


int main()
{
    cin>>amount;
    vector<int> dp(amount+1,amount+1);//初始值也为amount + 1,是取不到的
    dp[0]=0;
    for(int i=0;i<dp.size();i++)
    {
        for(auto e:coins)
        {
            if(i-e<0) continue;
            dp[i]=min(dp[i],dp[i-e]+1);
        }
    }
    
    if(dp[amount]==amount+1) cout<<-1<<endl;
    else cout<<dp[amount];
}

dp数组定义：凑其前i金额需要的硬币数量。

初始值也为amount + 1,是取不到的

base case：自底向上思考，dp[0]为0：金额为0时就不再需要硬币了

选择：从硬币面值组合里面选

状态：假设前i-1个已经选完了，最后选一个正好凑完

状态转移： dp[i]=min(dp[i],dp[i-e]+1);需要判断i-e是否>0

滑雪

题目

【蓝桥杯C/C++】专题六：动态规划

【蓝桥杯C/C++】专题六：动态规划

代码

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int n,m;
int g[N][N];//不能存在有环图
int f[N][N];//所有从i,j开始滑的路径，属性是max
//集合分为四类，向上向右向左向下
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int dp(int x,int y)
{
    int &v=f[x][y];//引用即为取别名
    if(v!=-1) return v;//表示已经算过了
    v=1;//最小值为1
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&g[x][y]>g[a][b])
        v=max(v,dp(a,b)+1);
    }
    return v;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
            
    memset(f,-1,sizeof f);//初始化表示每个路径都没被算过
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp(i,j));
    cout<<res<<endl;
    return 0;
}

题解

本题考察使用记忆化搜索优化dp的算法

思路是：枚举路径上的每一个点，找到最大值，而每一个点又能分为四种小的递推的状态，因此可以使用动态规划来解决。

dp数组：使用一个二维数组来表示路径的长度

属性：最大值，满足条件即更新

记忆化搜索技巧：初始化数组表示没有被算过，如果已经被计算过就可以直接返回

汉罗塔

题目

【蓝桥杯C/C++】专题六：动态规划

题解

dfs

可以用dfs来搜索所有的情况取最大值

参数：

  1. index表示到第几层
  2. y表示枚举该层的第一个还是第二个数
  3. sum表示总和
#include<bits/stdc++.h>
using namespace std;

const int N=10;
int f[N][N];

int ans;
int n;
void dfs(int index,int y,int sum)
{
    if(index==n)
    {
        ans=max(ans,sum);
        return ;
    }
    
    dfs(index+1,y,sum+f[index+1][y]);
    dfs(index+1,y+1,sum+f[index+1][y+1]);
}


int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
        {
            cin>>f[i][j];
        }
        
    dfs(0,0,f[0][0]);
    cout<<ans<<endl;
}

dp

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

const int N=10;
int f[N][N];
int dp[N][N];//表示从i,j到最后一层路径中的最大数字之和
int n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
        {
            cin>>f[i][j];
        }
        
    for(int i=0;i<n;i++)
    {
        dp[n-1][i]=f[n-1][i];//处理边界
    }
    
    //从后往前枚举
    for(int i=n-2;i>=0;i--)
    {
        for(int j=0;j<=i;j++)
        {
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];//递推式
        }
    }
    cout<<dp[0][0]<<endl;
    

}

注意本题是从后往前枚举，根据dp数组的定义从i,j到最后一层路径中的最大数字之和，也就是要输出

dp[0][0]

01背包问题

题目

【蓝桥杯C/C++】专题六：动态规划

【蓝桥杯C/C++】专题六：动态规划

代码

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

const int N=10010;
int n,V;
int v[N],w[N];
int f[N][N];//从i个物品中选，体积不超过j

int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
        
    for(int i=1;i<=n;i++)
        for(int j=1;j<=V;j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j<v[i]) f[i][j]=f[i-1][j];
               // 能装，需进行决策是否选择第i个物品
            else{
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
        
    cout<<f[n][V]<<endl;
    
}

题解

【蓝桥杯C/C++】专题六：动态规划

摘花生

题目

【蓝桥杯C/C++】专题六：动态规划

【蓝桥杯C/C++】专题六：动态规划

代码

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

const int N=110;
int a[N][N];
int dp[N][N];//从(1,1)到(i,j)所有路径中能摘得花生最多的路径
int t;
int n,m;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
                
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
                
                
        cout<<dp[n][m]<<endl;
    }
    

}

题解

用闫式dp法来分析：

【蓝桥杯C/C++】专题六：动态规划

最长上升子序列

题目

【蓝桥杯C/C++】专题六：动态规划

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;

int a[N];
int dp[N];//表示以i结尾的最长上升子序列
int  n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
        
    for(int i=1;i<=n;i++)
        dp[i]=1;
        
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            dp[i]=max(dp[i],dp[j]+1);
        }
        
    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,dp[i]);
        
    cout<<res<<endl;
}

题解

【蓝桥杯C/C++】专题六：动态规划

总结

动态规划是一种非常重要的算法思想，它可以解决很多实际问题，并且在计算机科学领域中有着广泛的应用。通过本博客的学习，我们可以了解到动态规划的基本概念、算法原理和应用场景。

在实际应用中，动态规划算法可以用于解决很多优化问题，如背包问题、最长公共子序列问题、最短路径问题等。学习动态规划算法不仅可以提高算法设计和解决问题的能力，还可以帮助我们更好地理解计算机科学中的一些基本概念和方法。

总之，动态规划算法是一种非常重要的算法思想，需要我们不断地学习和实践，才能更好地掌握它的精髓，并将其应用到实际问题中。希望本博客能够为读者提供一些启示和帮助，促进大家在算法学习和实践中的进步和成长。也祝大家考出好成绩！！

【蓝桥杯C/C++】专题六：动态规划文章来源地址https://www.toymoban.com/news/detail-428940.html

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

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

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

相关文章

  • 【马蹄集】第十六周——动态规划专题

    【马蹄集】第十六周——动态规划专题

    难度：钻石    时间限制：1秒    占用内存：128M 题目描述 给出一个长度为 n n n 的序列 A A A ，选出其中连续且非空的一段使得这段和最大。 格式 输入格式：第一行是一个整数，表示序列的长度 n n n ；      第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i

    2024年02月11日
    浏览(64)
  • leetcode-打家劫舍专题系列(动态规划)

    leetcode-打家劫舍专题系列(动态规划)

    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动

    2024年04月14日
    浏览(43)
  • 【动态规划专栏】专题二：路径问题--------1.不同路径

    【动态规划专栏】专题二：路径问题--------1.不同路径

    本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。 💓博主csdn个人主页：小小unicorn ⏩专栏分类：动态规划专栏 🚚代码仓库：小小unicorn的代码仓库🚚

    2024年02月20日
    浏览(44)
  • 蓝桥杯丨动态规划

    蓝桥杯丨动态规划

    做你想做的，错的算我的 这里是Want595，欢迎光临我的世界 ~   目录 前言  一、斐波那契式 通项公式：f(n)=f(n-1)+f(n-2)  举例说明 爬楼梯  骨牌铺方格  一只小蜜蜂 二、背包问题 通项公式：f(i,j)=max(f(i-1,j),f(i-1（或i）,j-w(i))+v(i))  举例说明  0-1背包问题  完全背包问题  矿工

    2024年02月11日
    浏览(35)
  • 【蓝桥杯-筑基篇】动态规划

    【蓝桥杯-筑基篇】动态规划

    🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 1.最大连续子段和 2.LCS 最大公共子序列 3.LIS 最长上升子序列 4.数塔 5.最大子矩阵和 6.背包问题 ①01背包问题 ②完全背包 这段代码是一个求最大子数组和的算法，使用的是动态规划的思想。下面是代码的解释： 首先定义了一个

    2023年04月24日
    浏览(71)

  • 【蓝桥杯/动态规划】数的计算

    题目描述 输入一个自然数 n (n≤1000)n (n leq 1000) n   ( n ≤ 1 0 0 0 ) ，我们对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止。 问总共可以产生多少个数。

    2024年02月01日
    浏览(47)
  • 蓝桥杯动态规划基础篇（一）

    蓝桥杯动态规划基础篇（一）

    动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、

    2024年02月03日
    浏览(37)
  • 蓝桥杯（路径 动态规划 C++）

    蓝桥杯（路径 动态规划 C++）

     思路： 1、利用动态规划的思想。 2、用f[i]来记录从第一个点到第i个点的最短距离。 3、f[i]赋值分两种情况，第一种：f[i]为0的时候，也就是第一种刚到i点的情况，记录其距离为最小公倍数；第二种：f[i]已经有值了，比较新的点到其距离和之前点到其距离，取小的赋值。

    2024年02月07日
    浏览(35)
  • 蓝桥杯-动态规划-子数组问题

    蓝桥杯-动态规划-子数组问题

    目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得： 最重要的还是状态表示，我们需要根据题的意思，来分析出不同的题，不同的情况，来分析需要多少个状态 乘积最大数组 1.状态表示 dp[i]:到达i位置的最大乘积子数组。

    2024年02月05日
    浏览(34)
  • 【动态规划专栏】专题二：路径问题--------6.地下城游戏

    【动态规划专栏】专题二：路径问题--------6.地下城游戏

    本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。 💓博主csdn个人主页：小小unicorn ⏩专栏分类：动态规划专栏 🚚代码仓库：小小unicorn的代码仓库🚚

    2024年02月22日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包