算法竞赛备赛之动态规划训练提升,DP基础掌握

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

算法竞赛备赛之动态规划训练提升,DP基础掌握,2023暑期算法集训,算法,动态规划,c++,蓝桥杯,acwing,竞赛

1.背包问题

1.1.01背包问题

01背包问题是在M件物品中选择若干件放在空间为W的背包中,每件物品的体积为W1,W2至Wn,价值为P1,P2至Pn,01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。

01背包问题常常采用动态规划的方法去求解,状态转移方程为:F(W,i)=max{F(W,i-1),F(W-Wi,i)},表示前i种物品装进容量为W的背包里面获取的最大价值。

2.01背包问题

有N件物品和一个容器是V的背包。每件物品只能使用一次。

第i件物品的体积vi,价值wi。

求解将哪些物品加入背包,使得总价值最大。

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int v[N], w[N];
int f[N][N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j--)
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    
    cout << f[n][m] << endl;
        
    return 0;
}

一维数组形式:

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int v[N], w[N];
int f[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1;i <= n; 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.完全背包问题

完全背包问题是指有N件物品和一个容量为V的背包,第i件物品的重量为weight[i],价值为value[i],每件物品有无限个,求怎样可以使背包物品价值总量最大。

完全背包问题与01背包问题大致相同,唯一不同的地方体现在遍历顺序方面,倒序遍历可避免一件物品重复选取。

3.完全背包问题

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int v[N], w[N];
int f[N][N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            for(int k = 0;k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    
    cout << f[n][m] << endl;
    
    return 0;
}

但是上面的代码很容易就超时,时间复杂度比较大。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int v[N], w[N];
int f[N][N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
           
    cout << f[n][m] << endl;
    
    return 0;
}

改成一维数组形式:

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int v[N], w[N];
int f[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1;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.3.多重背包问题

多重背包问题是在M种物品中选择若干件放在容量为W的背包中,每种物品有无限多个,01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。

4.多重背包问题I

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。

多重背包的暴力解法:

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 110;
​
int n, m;
int v[N], w[N], s[N];
int f[N][N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        scanf("%d%d%d", &v[i], &w[i], &s[i]);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            for(int k = 0;k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

5.多重背包问题II

有N种物品和一个容器是V的背包

第i种物品最多有s件,每件体积是vi,价值是wi。

求解将哪些物品装入背包,可以使得物品总体积和不超过背包的容量,且价值总和最大。

数据范围:增加到2000

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 25000;
​
int n, m;
int v[N], w[N];
int f[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    int cnt = 0;
    
    for(int i = 1;i <= n; i++)
    {
        int a, b, s;
        scanf("%d%d%d", &a, &b, &s);
        
        int k = 1;
        while(k <= s)
        {
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        
        if(s > 0)
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    
    n = cnt;
    
    for(int i = 1;i <= n; 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;
}

9.分组背包问题

有 NN 组物品和一个容量是 VV 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 110;
​
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
    {
        scanf("%d", &s[i]);
        for(int j = 0;j < s[i]; j++)
            scanf("%d%d", &v[i][j], &w[i][j]);
    }
    
    for(int i = 1;i <= n; i++)
        for(int j = m;j >= 0; j--)
            for(int k = 0;k < s[i]; k++)
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
    
    return 0;
}

2.线性DP

898.数字三角形

给定一个数字三角形,从顶部出发,在每一个结点可以选择移动至其左下方或者右下方的结点,一直走到底层,要求找出一条路径,是路径上的数字之和最大。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 510, INF = 1e9;
​
int n;
int a[N][N];
int f[N][N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= i; j++)
            scanf("%d", a[N][N]);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= i; j++)
            f[i][j] = -INF;
    
    f[i][j] = a[1][1];
    
    for(int i = 2;i <= n; i++)
        for(int j = 1;j <= i; j++)
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    
    int res = -INF;
    for(int i = 1;i <= n; i++)
        res = max(res, f[n][i]);
    
    printf("%d\n", res);
    return 0;
}

895.最长上升序列I

给定一个长度为N,求数值严格单调递增的子序列的长度最长是多少。

状态表示f[i] 集合:所有以第i个数结尾的上升子序列。属性:Max所有的上升子序列

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
int n;
int a[N], f[N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
        scanf("%d", &a[i]);
    
    for(int i = 1;i <= n; i++)
    {
        f[i] = 1;//只有a[i]一个数
        f(int j = 1;j < i; j++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for(int i = 1;i <= n; i++)
        res = max(res, f[i]);
    
    printf("%d\n", res);
    return 0;
}

将要输出的序列打印出来:

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
​
int n;
int a[N], f[N], g[N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
        scanf("%d", &a[i]);
    
    for(int i = 1;i <= n; i++)
    {
        f[i] = 1;
        g[i] = 0;
        for(int j = 1;j < i; j++)
            if(a[j] < a[j])
            {
                f[i] = f[j] + 1;
                g[i] = j;
            }
    }
    
    int k = 1;
    for(int i = 1;i <= n; i++)
        if(f[k] < f[i])
            k = 1;
    
    printf("%d\n", f[k]);
    
    for(int i = 0, len = f[k];i < len; i++)
    {
        printf("%d ", a[k]);
        k = g[k];
    }
    return 0;
}

896.最长上升子序列II

数据范围扩展到100000

897.最长公共子序列

第一个序列的前i个字母,和第二个序列前j个字母构成的子序列比较

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 1010;
​
int n, m;
int a[N], b[N];
int f[N][N];
​
int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a+1, b+1);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

899.编辑距离

给定个长度不超过10的字符串以及次询问,每次询问给出一个字符串和一个操作次数上限。

对于每次询问,请你求出给定的个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
int main()
{
    
    return 0;
}

3.区间DP

282.石子合并

设有 NN 堆石子排成一排,其编号为 1,2,3,…,N1,2,3,…,N。

每堆石子有一定的质量,可以用一个整数来描述,现在要将这 NN 堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2, 我们可以先合并 1、2堆,代价为 4,得到 4 5 2, 又合并 1、2 堆,代价为 9,得到 9 2 ,再合并得到 11,总代价为 4+9+11=24;

如果第二步是先合并 2、3 堆,则代价为 7,得到 4 7,最后一次合并代价为 11,总代价为 4+7+11=22。

问题是:找出一种合理的方法,使总的代价最小,输出最小代价。

#include<iostream>
#include<algorithm>
​
using namespace std;
​
const int N = 310;
​
int n;
int s[N];
int f[N][N];
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++)
        scanf("%d", &s[i]);
    
    for(int i = 1;i <= n; i++)
        s[i] += s[i - 1];
    
    for(int len = 2;len <= n; len++)
        for(int i = 1;i + len - 1 <= n; i++)
        {
            int l = i, r = len + i - 1;
            f[l][r] = 1e8;
            for(int k = l;k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    
    printf("%d\n", f[1][n]);
    return 0;
}

4.计数类DP

敬请期待

5.数位统计DP

338.计数问题

给定两个整数 a和 b,求 a 和 b 之间的所有数字中 0∼9的出现次数。

分别求出1的每一位上出现的次数

#include <bits/stdc++.h>
​
using namespace std;
int num[10];
​
int power10(int k)
{
    int res = 1;
    while(k){
        res *= 10;
        k --;
    }
    return res;
}
​
int getnum(int num[],int x,int y)
{
    int res = 0;
    for(int i = x;i <= y;i ++){
        res = res * 10 + num[i];
    }
    return res;
}
​
int solve(int n,int x)//求1~n中x的出现次数
{
    if(n == 0) return 0;
    int tmp = n,p = 0,res = 0,t;
    while(tmp){//获取数字n的每一位
        p ++;
        tmp /= 10;
    }
    tmp = n,t = p;
    while(tmp){//获取数字n的每一位
        num[t --] = tmp % 10;
        tmp /= 10;
    }
    for(int i = 1;i <= p;i ++){//求x在第i位中的出现次数
        if(x == 0 && i != 1){//0不可能在第一位出现
            res = res + (getnum(num,1,i - 1) - 1) * power10(p - i);
            if(num[i] < 1) res = res + getnum(num,i + 1,p) + 1;
            else res += power10(p - i); 
        }
        else if(x != 0){
            res = res + getnum(num,1,i - 1) * power10(p - i);
            if(num[i] == x) res += getnum(num,i + 1,p) + 1;
            else if(num[i] > x) res += power10(p - i); 
​
        }
    }
    return res;
}
​
int main()
{
    int a,b;
    while(cin >> a >> b,a || b){
        if(a > b) swap(a,b);
        int ans1[10] = {0},ans2[10] = {0};
        for(int i = 0;i < 10;i ++){
            int t1 = solve(b,i),t2 = solve(max(a - 1,1),i);
            if(a == 1) t2 = 0;
            cout << t1 - t2 << ' ';
        }
        cout << '\n';
    }
    return 0;
}

6.状态压缩DP

291.蒙德里安的梦想

求把 N×M 的棋盘分割成若干个 1×2 的长方形,有多少种方案。

例如当 N=2,M=4 时,共有 5 种方案。当 N=2,M=3 时,共有 3 种方案。

如下图所示:

算法竞赛备赛之动态规划训练提升,DP基础掌握,2023暑期算法集训,算法,动态规划,c++,蓝桥杯,acwing,竞赛

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 12, M = 1 << N;
​
int n, m;
long long f[N][M];
bool st[M];
​
int main()
{
    while(cin >> n >> m, n || m)
    {
        memset(f, 0, sizeof(f));
        
        for(int i = 0;i < 1 << n; i++)
        {
            st[i] = true;
            int cnt = 0;
            for(int j = 0;j < n; j++)
                if(i >> j & 1)
                {
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            
            if(cnt & 1) st[i] = false;
        }
        
        f[0][0] = 1;
        for(int i = 1;i <= m; i++)
            for(int j = 0;j < 1 << n; j++)
                for(int k = 0;k < 1 << n; k++)
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];
        
        cout << f[m][0] << endl;
    }
    
    return 0;
}

91. 最短Hamilton路径

给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

#include<iostream>
#include<algorithm>
#icnlude<cstring>
​
using namespace std;
​
const int N = 20, M = 1 << N;
​
int n;
int w[N][N];
int f[M][N];
​
int main()
{
    cin >> n;
    for(int i = 0;i < n; i++)
        for(int j = 0;j < n; j++)
            cin >> w[i][j];
    
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for(int i = 0;i < 1 << n; i++)
        for(int j = 0;j < n; j++)
            if(i >> j & 1)
                for(int k = 0;k < n; k++)
                    f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    
    cout << f[(1 << n) - 1][n - 1] << endl; 
    return 0;
}

7.树形DP

285.没有上司的舞会

Ural 大学有 N 名职员,编号为 1∼N。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

状态表示:集合所有从以u为根的子树中选择,并且不选u这个点的方案

所有从以u为根的子树中选,并且选择u这个点的方案

#include<iostream>
#include<cstring>
#include<algorithm>
​
using namespace std;
​
const int N = 6010;
​
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];
​
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
​
void dfs(int u)
{
    f[u][1] = happy[u];
    
    for(int i = h[u];i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}
​
int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n; i++) scanf("%d", &happy[i]);
    
    memset(h, -1, sizeof(h));
    for(int i = 0;i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        has_father[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root]) root++;
    
    dfs(root);
    
    printf("%d\n", max(f[root][0], f[root][1]));
    
    return 0;
}

8.记忆化搜索

记忆化搜索是一种优化搜索算法的方法,通过将搜索过程可视化,可以快速找到目标节点。在记忆化搜索中,首先将搜索过程记录在一个记忆表中,然后在搜索时检查记忆表以寻找目标节点。这种方法可以大大减少搜索时间,特别是在具有大量节点的图中。

记忆化搜索通常用于解决诸如图匹配、最短路径和最小生成树等问题。在实际应用中,记忆化搜索可以通过动态规划、散列和查表等技术实现。

901.滑雪

给定一个R行C列的矩阵,表示一个矩形网格滑雪场。

矩阵中第i行第1列的点表示滑雪场的第i行第j列区域的高度。

一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。

当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。文章来源地址https://www.toymoban.com/news/detail-719046.html

#include<iostream>
#include<algorithm>
#include<cstring>
​
using namespace std;
​
const int N = 310;
​
int n, m;
int h[N][N];
int f[N][N];
​
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;
    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 && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}
​
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            scanf("%d", &h[i][j]);
    
    memset(f, -1, sizeof(h));
    
    int res = 0;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            res = max(res, dp(i, j));
    
    printf("%d\n", res);
    return 0;
}

到了这里,关于算法竞赛备赛之动态规划训练提升,DP基础掌握的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯备赛之动态规划篇——涂色问题(区间DP)

    2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现) 2023第十四届蓝桥杯模拟赛第三期个人题解(Java实现) 蓝桥杯备赛之动态规划篇——背包问题 蓝桥杯真题——单词分析(Java实现) 😘😘 哈喽,大家好!这里是蓝桥杯系列文章的动态规划章节🔥🔥,今天要讲解的是区

    2024年01月23日
    浏览(48)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(48)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(50)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(45)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(49)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(56)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(48)
  • 算法——动态规划(DP,Dynamic Programming)

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年02月02日
    浏览(51)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包