GESP6级语法知识（二）：动态规划算法（二）

最小路径和;

//最小路径和 
#include<iostream>
using namespace std;
const int N=100;
int dp[N][N],value[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)//录入初始数字矩阵 
for(int j=1;j<=m;j++)
cin>>value[i][j];
for(int i=1;i<=n;i++)// 初始化最上方第一行 
dp[1][i]=dp[1][i-1]+value[1][i];
for(int i=1;i<=n;i++)// 初始化最左边第一列 
dp[i][1]=dp[i-1][1]+value[i][1]; 
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)// 开始进行状态转移（即填写dp表） 
dp[i][j]=min(dp[i][j-1],dp[i-1][j])+value[i][j];
cout<<dp[n][m]<<endl; 
return 0;
}

最小路径和（一维数组）：

#include<iostream>
using namespace std;
const int N=100000;
int dp[N];
int n,m;
int main()
{
int n,m,temp;
cin>>n>>m;
for(int i=1;i<=m;i++){//第一步：初始化 
cin>>temp;
dp[i]=dp[i-1]+temp;
}
for(int i=2;i<=n;i++)//第二步
{
cin>>temp;//得到当前值 
dp[1]+=temp;//第二步中的第①步：求第一个值 
for(int j=2;j<=m;j++){//第二步中的第②步：求其余值 
cin>>temp;
dp[j]=min(dp[j-1],dp[j])+temp;
}
}
cout<<dp[m];//输出最终结果 
return 0;
}

走方格：

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[10005][10005];
int main()
{
        cin>>n>>m;
dp[0][0]=0;
        for(int i=1; i<=n; i++)
            dp[i][0]=1;
        for(int j=1; j<=m; j++)
            dp[0][j]=1;//初始化
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];//动态规划转移方程
            }
        cout<<dp[n][m];
        return 0;
}

走方格（优化为一维数组）

#include<iostream>
using namespace std;
const int N=100000;
const int MOD=100000007;
int dp[N];
int n,m;
void DP()
{
dp[1]=1;// 初始化第一个格子
for(int i=1;i<=n;i++)// 通过二重循环遍历整个表单以更新dp[N]中的数据
for(int j=2;j<=m;j++)
dp[j]=(dp[j-1]+dp[j])%MOD;
}
int main()
{
cin>>n>>m;
DP();
cout<<dp[m];
return 0;
}

最长上升子序列：

#include<cstdio>
#include<algorithm>    //这个头文件可以使用max(,),*max_element(,)
using namespace std;    //它们的含义分别是：求两者最大；求数组最大
int n,a[1002],f[1002];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);   //输入
        f[i]=1;              //以第i个数为末尾的上升序列最初长度为1
    }
    for(int i=1;i<=n;i++)         //枚举i的位置
        for(int j=1;j<i;j++)   //在i的前面找j的位置
            if(a[i]>a[j]) //如果满足条件，则第i个数可以放在j后边
                f[i]=max(f[j]+1,f[i]);//取较大的一种再放
    printf("%d",*max_element(f+1,f+n+1));//从 F[1]到F[n] 找最大值
    return 0;
}

原文地址：https://blog.csdn.net/weixin_60445850/article/details/145281974

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！