大家好，我是wangmy。
众所周知动态规划将原问题分解成若干个子问题，再把子问题分解成若干更多子问题。先求解子问题，再从这些子问题的解得到原问题的解。
今天我给大家分享一下动态规划的几道题和参考代码。
数字三角形
题目描述(Description)
编辑
输入格式(Format Input)
第一行一个整数N(输出格式(Format Output)
一个整数，表示一路上所有数的最大和，结果不会超过int64输入样例(Sample Input)
4
1
3 2
4 10 1
4 3 2 20
输出样例(Sample Output)
24
限制(Restrictions)
时间限制(Time Limit): 1000 ms内存限制(Memory Limit): 65536 KB参考代码：
#include
using namespace std;
//状态 f[i][j]:(i,j)的最大值
//转移方程式：f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j]
long long n,a[1010][1010],f[1010][1010];
int main()
{
scanf("%lld",&n);
for(int i=1;ians)
{
ans=f[n][i];
}
}
printf("%lld",ans);
return 0;
}最长上升子序列
题目描述(Description)
给定一个长度为 N 的整数序列 A
找到一组最长的整数序列 x 满足：
1
A[x1]
即寻找 A 的一个最长子序列，满足：
该子序列中每个元素递增
输入格式(Format Input)
第一行一个整数N(N输出格式(Format Output)
一行 表示最长递增子序列的长度输入样例(Sample Input)
6
1 6 2 5 4 7
输出样例(Sample Output)
4
限制(Restrictions)
时间限制(Time Limit): 1000 ms内存限制(Memory Limit): 65536 KB参考代码：
#include
using namespace std;
//f[i]以a[i]结尾的最大上升子序列长度
//f[i] = max(f[i], f[j] + 1), j > n;
for(int i = 1; i 最长公共子序列
题目描述(Description)
给定两个整数序列 A 和 B
序列中每个数都在int范围之内
寻找一个最长的整数序列 X，满足：
X 是 A 的子序列
X 是 B 的子序列
输入格式(Format Input)
第一行：序列A的长度 第二行：给出序列A 第三行：序列B的长度 第四行：给出序列B
长度输出格式(Format Output)
只有一行：表示最长的公共子序列的长度输入样例(Sample Input)
6
1 6 2 5 4 7
7
0 1 2 5 5 2 7
输出样例(Sample Output)
4
限制(Restrictions)
时间限制(Time Limit): 1000 ms内存限制(Memory Limit): 65536 KB参考代码：
#include
using namespace std;
int n, m, a[1001], b[1001], dp[1001][1001];
int main()
{
cin >> n;
for(int i = 1; i > m;
for(int i = 1; i dp[i-1][j])
dp[i][j] = dp[i][j-1];
else
dp[i][j] = dp[i-1][j];
}
}
}
cout 装箱问题
题目描述(Description)
有一个箱子容量为V(正整数,0 ≤ V ≤ 20000),同时有n个物品(0
输入格式(Format Input)
输入有若干行。第一行：一个整数，表示箱子容量V；第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。输出格式(Format Output)
输出只有一行数据，该行只有一个数，表示最小的箱子剩余空间。输入样例(Sample Input)
24
6
8
3
12
7
9
7
输出样例(Sample Output)
0
限制(Restrictions)
时间限制(Time Limit): 1000 ms内存限制(Memory Limit): 65536 KB参考代码：
#include
using namespace std;
int m,n;// m即箱子容量V
int f[20010];
int w[40];
int main(){
int i,j;
scanf("%d%d",&m,&n);
for(i=1;i=w[i];j--){
if(f[j]今天的分享到此结束，我们下次再见。（希望大家有自己的思考，不要一味着抄代码）
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
