晴问算法动态规划（简单）-Toy模板网

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

动态规划的递归写法和递推写法

斐波那契数列II

题目描述

给定正整数�，求斐波那契数列的第�项�(�)。

令�(�)表示斐波那契数列的第�项，它的定义是：

当�=1时，�(�)=1；

当�=2时，�(�)=1；

当�>2时，�(�)=�(�−1)+�(�−2)。

输入描述

一个正整数�（1≤�≤104）。

输出描述

斐波那契数列的第�项�(�)。

由于结果可能很大，因此将结果对10007取模后输出。

#include <cstdio>
int fib[10001]={0};

int main() {
    int n;
    scanf("%d", &n);
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2])%10007;
    }
    printf("%d", fib[n]);
    return 0;
}

数塔II

题目描述

晴问算法动态规划（简单）,动态规划,算法,动态规划

数塔就是由一堆数字组成的塔状结构，其中第一行1个数，第二行2个数，第三行3个数，依此类推。每个数都与下一层的左下与右下两个数相连接。这样从塔顶到塔底就可以有很多条路径可以走，现在需要求路径上的数字之和的最大值。

例如在上图中，5->8->12->10与5->3->16->11这两条路径上的数字之和都是35，是所有路径中的最大值。

输入描述

第一行一个正整数�（1≤�≤100），表示数塔的层数。

接下来�行为数塔从上到下的每一层，其中第�层有�个正整数，每个数都不超过1000。

输出描述

从塔顶到塔底的所有路径中路径上数字之和的最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a[102][102]={0};
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
    }
    cout<<a[1][1];
    return 0;
}

上楼II

题目描述

我打算走楼梯上楼，共有�级台阶。

我身轻如燕，所以每次都可以选择上一级台阶或者两级台阶。

问有多少种上楼的方式。

例如当�=3时，共有三种方式上楼：

一级 => 一级 => 一级；
一级 => 二级；
二级 => 一级。

输入描述

一个正整数�（1≤�≤104），表示台阶级数。

输出描述

一个整数，表示上楼的方案数。

由于结果可能很大，因此将结果对10007取模后输出。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[100001];
    a[1]=1;
    a[2]=2;
    for (int i = 3; i <= n; i++) {
        a[i] = (a[i - 1] + a[i - 2])%10007;
    }  
    cout<<a[n];
    return 0; 
}

最大连续子序列和

题目描述

现有一个整数序列�1,�2,...,��，求连续子序列��+...+��的最大值。

输入描述

第一行一个正整数�（1≤�≤104），表示序列长度；

第二行为用空格隔开的�个整数��（−105≤��≤105），表示序列元素。

输出描述

输出一个整数，表示最大连续子序列和。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int a,b;
    int max1=-2222222;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(i==1) b=a;
        else b=max(a,a+b);
        max1=max(max1,b);

    }
    cout<<max1;
    return 0;

}

最长不下降子序列（LIS）

最长上升子序列

题目描述

现有一个整数序列�1,�2,...,��，求最长的子序列（可以不连续），使得这个子序列中的元素是非递减的。输出该最大长度。

输入描述

第一行一个正整数�（1≤�≤100），表示序列长度；

第二行为用空格隔开的�个整数��（−105≤��≤105），表示序列元素。

输出描述

输出一个整数，表示最大长度。

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[1001]={0};
	int dp[1001]={0};
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<=a[i]){
				dp[i]=max(dp[i],dp[j]+1);
				
			}

		}
		if(dp[i]>maxn) maxn=dp[i];
	}
	cout<<maxn;
	return 0;
}

最长公共子序列（LCS）

最长公共子序列

题目描述

现有两个字符串�1与�2，求�1与�2的最长公共子序列的长度（子序列可以不连续）。

输入描述

第一行为字符串�1，仅由小写字母组成，长度不超过100；

第一行为字符串�2，仅由小写字母组成，长度不超过100。

输出描述

输出一个整数，表示最长公共子序列的长度。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    int dp[102][102]={0};
    for(int i=1;i<=a.length();i++){
        for (int j = 1; j <= b.length(); j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    cout<<dp[a.length()][b.length()];
    return 0;
}

最长回文子串

题目描述

现有一个字符串�，求�的最长回文子串的长度。

输入描述

一个字符串�，仅由小写字母组成，长度不超过100。

输出描述

输出一个整数，表示最长回文子串的长度。

//中点扩散算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
    string str;
    getline(cin,str);
    int res=0;
    for(int i=0;i<str.length();i++)
    {
        int l=i-1,r=i+1;//判断奇数长度回文串
        while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);
        l=i,r=i+1;//判断偶数长度回文串
        while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
        res=max(res,r-l-1);
    }
    cout<<res<<endl;
    return 0;
}

背包问题

01背包问题

题目描述

有�件物品，每件物品的重量为��，价值为��。现在需要选出若干件物品放入一个容量为�的背包中（每件物品至多选一次），使得在选入背包的物品重量之和不超过容量�的前提下，让背包中物品的价值之和最大，求最大价值。

输入描述

第一行两个整数�、�（1≤�≤100,1≤�≤103），分别表示物品数量、背包容量；

第二行为用空格隔开的�个整数��（1≤��≤10），表示物品重量；

第三行为用空格隔开的�个整数��（1≤��≤10），表示物品价值。

输出描述

输出一个整数，表示最大价值。

#include<bits/stdc++.h>
using namespace std ;
int ti[1005] , pri[1005] ;
int f[1005][1005] ;
int main()
{
	int t , m ;
	cin >> m>> t ;
    for(int i = 1 ; i <= m ; ++i){
        cin >> ti[i];
    }
    for(int i = 1 ; i <= m ; ++i){
        cin >> pri[i];
    }
	for(int i = 1 ; i <= m ; ++i)
	{
        for(int j = 1 ; j <= t ; ++j)
		{
			f[i][j] = f[i - 1][j] ;
            if(j >= ti[i]) 
				f[i][j] = max(f[i][j], f[i - 1][j - ti[i]] + pri[i]) ;
        }
    }
    cout << f[m][t] ;
	return 0 ;
}

完全背包问题

题目描述

有�种物品，每种物品的重量为��，价值为��。现在需要选出若干件物品放入一个容量为�的背包中（每种物品可以选任意次），使得在选入背包的物品重量之和不超过容量�的前提下，让背包中物品的价值之和最大，求最大价值。

输入描述

第一行两个整数�、�（1≤�≤100,1≤�≤103），分别表示物品数量、背包容量；

第二行为用空格隔开的�个整数��（1≤��≤100），表示物品重量；

第三行为用空格隔开的�个整数��（1≤��≤100），表示物品价值。

输出描述

输出一个整数，表示最大价值。

#include<bits/stdc++.h>
using namespace std;
int a[1002]={0},b[1002]={0};
int f[1002]={0};
int main(){
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=v;j++){
			f[j] = max(f[j], f[j - a[i]] +b[i]);
        }
    }
    cout << f[v];
    return 0;
}

01背包问题的方案数

题目描述

有�件物品，每件物品的重量为��。现在需要选出若干件物品放入一个容量为�的背包中（每件物品至多选一次），使得选入背包的物品重量之和恰好等于容量�。求满足条件的方案数。

输入描述

第一行两个整数�、�（1≤�≤100,1≤�≤103），分别表示物品数量、背包容量；

第二行为用空格隔开的�个整数��（1≤��≤10），表示物品重量。

输出描述

输出一个整数，表示方案数。由于结果可能很大，因此将结果对10007取模后输出。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,M;
	cin>>N>>M;
	int a[1005],dp[10050];
	for(int i=1;i<=N;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for(int i=1;i<=N;i++){
		for(int j=M;j>=a[i];j--){
			dp[j]=(dp[j]+dp[j-a[i]])%10007;
		}
	}
	cout<<dp[M];
	return 0;
}

总结

最小消耗能量

题目描述

现有�个从左至右摆放着的高台（编号为从1到n），每个高台有各自的高度ℎ�。假设闯关者当前处于第�个高台，那么可以选择跳到第�+1或第�+2个高台（闯关者能够跳任意高度）。如果从第�个高台跳到第�个高台，那么将会消耗闯关者|ℎ�−ℎ�|点能量。问从第1个高台出发、到达第�个高台的过程中需要消耗的最小能量。

输入描述

第一行一个整数�（1≤�≤104），表示高台个数。

第二行为用空格隔开的�个整数ℎ�（1≤ℎ�≤100），表示各高台的高度。

输出描述

一个整数，表示需要消耗的最小能量。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[10002];
    int dp[10002];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        dp[0]=dp[1]=0;
        dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
        dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n];
    return 0;

}

矩阵最大权值

题目描述

现有一个�∗�大小的矩阵，矩阵中的每个元素表示该位置的权值。现需要从矩阵左上角出发到达右下角，每次移动只能向右或者向下移动一格。求最后到达右下角时路径上所有位置的权值之和的最大值。

输入描述

第一行两个整数�、�（1≤�≤100,1≤�≤100），分别表示矩阵的行数和列数；

接下来�行，每行�个整数（−100≤整数≤100），表示矩阵每个位置的权值。

输出描述

一个整数，表示权值之和的最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[101][101];
    int dp[101][101]={0};
    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[1][1]=a[1][1];
            if(i==1&&j!=1){
                dp[i][j]=dp[i][j-1]+a[i][j];
            }
            if(i!=1&&j==1){
                dp[i][j]=dp[i-1][j]+a[i][j];
            }
            if(i!=1&&j!=1){
                dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

最小涂色成本

题目描述

现有�张不同大小的白纸排成一排，每张白纸可以涂成红、黄、蓝三种颜色之一，但不能有连续两张白纸涂成相同的颜色。假设给第�张白纸涂红色需要消耗的成本为��，涂黄色需要消耗的成本为��，涂蓝色需要消耗的成本为��，求把�张白纸全部涂色需要的最小成本。

输入描述

第一行一个整数�（1≤�≤104），表示白纸张数；

接下来�行，每行三个整数，表示第�张白纸分别涂红、黄、蓝三种颜色需要消耗的成本��、��、��（1≤��≤100,1≤��≤100,1≤��≤100）。

输出描述

一个整数，表示最小成本。文章来源地址https://www.toymoban.com/news/detail-857851.html

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[10001][4];
    int dp[10001][4];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            if(i==1) dp[i][j]=a[i][j];
            else{
                if(j==1) dp[i][1]=a[i][j]+min(dp[i-1][2],dp[i-1][3]);
                if(j==2) dp[i][2]=a[i][j]+min(dp[i-1][1],dp[i-1][3]);
                if(j==3) dp[i][3]=a[i][j]+min(dp[i-1][1],dp[i-1][2]);
            }  
        }
    }  
    cout<<min(min(dp[n][1], dp[n][2]), dp[n][3]);
    return 0;  

}

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