＜算法学习＞动态规划-Toy模板网

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

一、超级台阶问题。

二、矩阵最短路径

三、最长递增子序列

四、最大连续子段和

五、最长公共子序列

六、0-1背包问题

七、找零问题

动态规划的基础知识和例题在这篇文章里列的很详细。

C++动态规划详解

在这里针对每道例题的解法多解释一下，方便以后复习回看。

一、超级台阶问题。

这里需要强调一个问题。

其实dp[0]到底为0还是为1的争议并没什么必要，大部分认为dp[0]=1的结论也是根据答案倒推的。如果0代表第0级台阶那么认为方案数为0也未尝不可，可是按照答案又解释不通。

所以最好的理解方法是不考虑dp[0]，因为dp[0]没有实际意义。我们直接考虑走一级台阶和两级台阶的方案数，即dp[1]=1，dp[2]=2。这两步毫无疑问，那么根据这两步再推后面的就好了。

循环时i从3开始取即可。

按照参考博文中分析的思路，最容易想到的普遍解法如下。

#include <iostream>
#include <cmath>
using namespace std;
#define N 10000
int dp[N];  //dp[i]代表爬上第i级台阶的所有方案数
int climb(int n)
{
    dp[1]=1;  //n=1和n=2作为递推条件
    dp[2]=2;
    if(n<=2) return dp[n];  //n<=2时直接返回
    else
    {
        for(int i=3;i<=n;i++)  //n>=3时递推
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];  //返回dp[n]即为到第n阶时总共的方案数
    }
}
int main()
{
    int T; //T组用例
    cin>>T;
    while(T--)
    {
        int num;
        cin>>num;
        cout<<climb(num)<<endl;
    }
    return 0;
}

文章中的方法是为了提高空间效率的改进版。和下面的代码等价，下面给出方便初学者理解的改进版代码。

#include <iostream>
#include <cmath>
using namespace std;
int dp[3]; //dp数组只有3个存储空间，相当于只保留每轮的结果
int climb(int n)
{
    dp[1]=1;  //递推初始条件 （dp[0]空着不用）
    dp[2]=2;
    if(n<=2) return dp[n]; //还是n<=2直接返回结果
    else
    {
        for(int i=3;i<=n;i++)  //递推过程
        {
            int temp=dp[1]+dp[2];  //设置临时变量计算dp[i]
            dp[1]=dp[2];  //将dp中后两个位置更新迭代（dp[0]空着不用）
            dp[2]=temp;
        }
        return dp[2]; //最终dp[n]的结果会赋给dp[2]，所以返回dp[2]即可
    }
}
int main()
{
    int T; //T组用例
    cin>>T;
    while(T--)
    {
        int num;
        cin>>num;
        cout<<climb(num)<<endl;
    }
    return 0;
}

二、矩阵最短路径

给出更为普遍的解题代码，可以自定义行列数。用随机数生成矩阵。

#include <iostream>
#include <stdlib.h>
#include <time.h>
#define N 10000
using namespace std;
int dp[N][N];
int matrix[N][N];
void shortest_road(int n,int m)
{
    dp[0][0]=matrix[0][0];//递推初始条件
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i==0 && j!=0) dp[i][j]=matrix[i][j]+dp[i][j-1];//第一行，只能从左边过来
            else if(i!=0 && j==0) dp[i][j]=matrix[i][j]+dp[i-1][j];//第一列，只能从上边过来
            else if(i!=0 && j!=0) dp[i][j]=matrix[i][j]+min(dp[i][j-1],dp[i-1][j]);
            //其他情况，可以从上面来，也可以从左边来
        }
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    srand((int)time(NULL));
    //生成n*m随机数矩阵
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int b=rand()%20;
            matrix[i][j]=b;
        }
    }
    //打印随机数矩阵
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            printf("%3d ",matrix[i][j]);
        }
        cout<<endl;
    }
    shortest_road(n,m);
    cout<<dp[n-1][m-1]<<endl;  //输出最短路径长度
    return 0;
}

三、最长递增子序列

题目对应的代码实现

#include <iostream>
using namespace std;
#define N 10000
int dp[N];  //dp[i]代表以a[i]结尾的最长子序列长度
int a[N];
int ans=0;
void make_dp(int n)
{
    dp[0]=1;  //递推初始条件
    for(int i=1;i<n;i++)
    {
        dp[i]=1;  //以当前a[i]为结尾的递增子序列长度最少为1
        for(int j=0;j<i;j++)
        {
            if(a[i]>a[j])  //试图更新以当前下标i对应的a[i]结尾的最大递增子序列长度
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);  //注意dp[i]的含义，所以这里相当于最后还要遍历一遍找到dp[]中的最大值
    }
}
int main()
{
    int n;
    cin>>n;
    getchar();
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        getchar();
    }
    make_dp(n);
    cout<<ans<<endl;
    return 0;
}

测试用例：

＜算法学习＞动态规划,算法学习,算法,学习,动态规划

此题目还有一种变式，要求最长连续递增子段长度

思路和不连续时的没有太大差异，只需要改变一下状态转移方程及分类条件即可。

代码如下：

#include <iostream>
using namespace std;
#define N 10000
int dp[N];  //dp[i]代表以a[i]结尾的最长子序列长度
int a[N];
int ans=0;
void make_dp(int n)
{
    dp[0]=1;  //递推初始条件
    for(int i=1;i<n;i++)  //只需单层循环即可
    {
        if(a[i]>a[i-1])  //这里和a[i-1]比较
        {
            dp[i]=dp[i-1]+1;
        }
        else dp[i]=1;  //只要小于前一个数，就要重新开始找递增序列
        ans=max(ans,dp[i]);  //注意dp[i]的含义，所以这里相当于最后还要遍历一遍找到dp[]中的最大值
    }
}
int main()
{
    int n;
    cin>>n;
    getchar();
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        getchar();
    }
    make_dp(n);
    cout<<ans<<endl;
    return 0;
}

测试用例：

＜算法学习＞动态规划,算法学习,算法,学习,动态规划

四、最大连续子段和

#include <iostream>
#define N 10000
using namespace std;
int dp[N]; //dp[i]代表以a[i]结尾的最大连续子段和
int a[N];
int main()
{
    int n;
    cin>>n;
    getchar();
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        getchar();
    }
    int res=a[0];  //初始化结果为a[0]
    dp[0]=a[0];
    for(int i=1;i<n;i++)
    {
        dp[i]=max(a[i],dp[i-1]+a[i]);  //状态转移方程
        res=max(res,dp[i]);  //试图更新最大值
    }
    cout<<res<<endl;
    return 0;
}

测试用例：

＜算法学习＞动态规划,算法学习,算法,学习,动态规划

如果想找到最大子段和对应的子段是从哪开始的，可以增加一个数组b，b[i]表示以a[i]结尾的最大子段的开头下标。在更新res的时候也要更新一下res对应的下标i，这样的话子段就是从b[i]到i的了

五、最长公共子序列

具体分析看这篇文章，写得特别好。

C++ 动态规划经典案例解析之最长公共子序列（LCS）_窥探递归和动态规划的一致性

下面是对代码的一些注释，便于以后复习。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define N 1000
int dp[N][N];
string s1;
string s2;
void LCS()
{
    for(int i=0;i<=s1.size();i++)  //初始化dp[][]数组，下标第0行第0列都为0
    {
        dp[i][0]=0;    //这里把s1作为行，s2作为列，所以要注意循环大小和初始化行列的[0]是否对应
    }
    for(int j=0;j<=s2.size();j++)
    {
        dp[0][j]=0;
    }

    for(int i=1;i<=s1.size();i++) //从下标为1处开始更新dp[][]，注意终止处加=
    {
        for(int j=1;j<=s2.size();j++)
        {
            if(s1[i-1]==s2[j-1])  //注意这里i-1和j-1的原因是dp数组是从下标为1处开始计的
                                //而s1和s2字符串是从下标为0处开始的
            {
                dp[i][j]=dp[i-1][j-1]+1;  //若要+1，直接用左上对角线处位置的dp数即可
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);  //否则比较上或左两条路的dp大小
            }
        }
    }
}
int main()
{
    cin>>s1;
    cin>>s2;
    LCS();
    for(int i=0;i<=s1.size();i++)
    {
        for(int j=0;j<=s2.size();j++)
        {
            cout<<dp[i][j]<<'\t';
        }
        cout<<endl;
    }
    cout<<"最长公共子序列:"<<endl;
    cout<<dp[s1.size()][s2.size()]; //注意dp数组是从1开始计的，故s1.size（）不用减1
    return 0;

}

六、0-1背包问题

题目描述：

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），求背包能够容纳的最大价值。

创建一个二维数组dp，存储每种情况下的最大价值。

行为物品0-n,列为背包剩余容量0-w，可知物品数为0和背包剩余容量为0，价值都是0，作为起始条件。

从上到下，从左到右遍历dp数组。当背包剩余容量大于当前物品容量时，可放可不放。若不放，还是dp[i-1][j]。若放，dp[i][j-w[i-1]]+p[i-1] （-1的原因是dp数组是从1开始计的，而w是从0开始的）。二者取更大值。

背包剩余容量小于物品容量，只能不放，即dp[i][j]=dp[i-1][j]。

#include <iostream>
#define N 1000
using namespace std;
int dp[N][N];  //dp[i][j]表示当前最大价值，横轴代表背包容量，纵轴代表物品个数
int w[N],p[N]; //物品的重量和价值数组
void package(int n,int v)
{
    for(int i=0;i<=n;i++) //初始化第0行和第0列为0（因为没物品和背包没容量）
    {
        dp[i][0]=0;
    }
    for(int j=0;j<=v;j++)
    {
        dp[0][j]=0;
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=v;j++)
        {
            if(j>=w[i-1])  //注意这里i-1的原因是dp数组是从1开始计的，而w是从0开始的
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-w[i-1]]+p[i-1]);//装的下，可装可不装
            }
            else dp[i][j]=dp[i-1][j];  //装不下，只能不装
        }
    }
}
int main()
{
    int n,v;
    cin>>n;
    cin>>v;
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>p[i];
    }
    package(n,v);
    cout<<dp[n][v]<<endl;
    return 0;
}

0-1背包的回溯方法和推导动画可以看这个视频：

【动态规划】背包问题

七、找零问题

题目描述：给你 k 种面值的钱币，面值分别为 c1, c2 … ck ，每种硬
币的数量无限，给⼀个总⾦额 amount ，问你最少需要⼏张钱币凑出这个
金额，如果不可能凑出，算法返回 -1 。

算法分析：

首先我们把所有提供的面值放入一个数组penny[]，并按面值从小到大排序，则penny[0]即为最小面值。

dp[][]数组的列代表要凑的钱值，行代表不同种类面值的纸币。

初始化dp数组时，先把钱值为0的第0列全部初始化为0，因为不需要凑钱，自然钱币张数为0.

接下来初始化第一行。设最终要凑的钱值为amount，最小的面值为penny[0]，则最多的钱币张数为amount/penny[0]。超过这个数的都当做无穷大，即没有解。

更新dp数组时，从上往下，从左往右遍历。

如果当前列（即要凑的钱值）大于penny[i-1]（这里-1是因为dp数组从1开始更新，而penny数组从0开始存储），则表示可以找此面值的零钱。此时有两种选择，找或不找。如果不找，那么钱币张数跟没有这个面值的钱币时一样，即dp[i-1][j]。如果找，那么钱币张数为dp[i][j-penny[i-1]]+1，其中1代表这张新面值的钱币，dp[i][j-penny[i-1]]代表要凑钱值减去这张面值后所要凑的钱所对应的最小钱币张数，之前已经求过。找和不找两种情况取更小值（找钱张数少的好）

如果当前列小于penny[i-1]，没法找该面值的零钱，只能不找，即dp[i][j]=dp[i-1][j]

注：可能有人会有疑问，为什么如果选择找当前面值的钱币，只+1张，可能+多张啊？

这种情况其实在该钱币所在行的后续列会出现，后续列更新的时候用了该张数+1列的值。所以其实所有情况已经考虑过了。

有关该问题的动画演示可以看这个链接：

最少硬币找零-动态规划 Coin Change Programming Dynamic Programming

下面是具体代码：

#include <iostream>
#include <algorithm>
#define N 10000
using namespace std;
int dp[N][N];
int penny[N];
int findchange(int s,int a)
{
    for(int i=0;i<=s;i++)  //初始化
    {
        dp[i][0]=0;
    }
    for(int j=0;j<=a;j++)
    {
        dp[0][j]=a/penny[0]+1;  //超过a/penny[0]相当于无穷大
    }

    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=a;j++)
        {
            if(j>=penny[i-1])  //可以尝试找零
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-penny[i-1]]+1);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    if(dp[s][a]>a/penny[0]+1) return -1;
    else return dp[s][a];
}
int main()
{
    int s,amount;  //零钱种数和需要找零的钱值
    cin>>s>>amount;
    for(int i=0;i<s;i++)
    {
        cin>>penny[i];
        getchar();
    }
    sort(penny,penny+s);

    cout<<findchange(s,amount)<<endl;
    return 0;

}

测试用例：

＜算法学习＞动态规划,算法学习,算法,学习,动态规划文章来源地址https://www.toymoban.com/news/detail-833088.html