三角形数字
f[i][j]表示从开始的位置到i，j位置的路径之和的最大值。 因为f[i][j]是要求的那个，所以我们要求出它的状态方程 f[i][j]=max(f[i-1][j-1] a[i][j],f[i-1][j] a[i][j]) ok，现在开始我们做这道题
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
int main()
{
int n;
while(cin>>n)
{vector<vector<int>> a(n 1,vector<int>(n 1));
vector<vector<int>> f(n 1,vector<int>(n 1,INT_MIN));//初始为最小值
for(int i=1;i<=n;i )
{
for(int j=1;j<=i;j )
{
cin>>a[i][j];
}
}
f[1][1]=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 ret=INT_MIN;
for(int i=1;i<=n; i)
{
if(f[n][i]>ret)
ret=f[n][i];
}
cout<<ret<<endl;}
return 0;
}优化：
代码语言：javascript复制cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<vector<int>> a(n 1,vector<int>(n 1));
vector<int> f(n 1,-1000);
for(int i=1;i<=n;i )
{
for(int j=1;j<=i;j )
{
cin>>a[i][j];
}
}
f[1]=a[1][1];
for(int i=2;i<=n;i )
{
for(int j=i;j>=1;--j)//从后往前不会被覆盖
{
f[j]=max(f[j-1] a[i][j],f[j] a[i][j]);
}
}
int ret=-1000;
for(int i=1;i<=n; i)//找出最大
ret=max(ret,f[i]);
cout<<ret<<endl;
return 0;
}最长上升子序列1
题目描述：从一段数据中选择最长的子序列，子序列是非递减的。求的是这个子序列的长度的最大值。 问题解决：f[i]表示以第i个数结尾的子序列的最大值。 方程计算：f[i]=max(f[i-1],f[i-2],f[i-3]…f[i-k]…f[0]) 1当然也可以在每个里面加1,注意：a[i-k]的值必须满足子序列的条件。
代码语言：javascript复制cpp#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> v(n),f(n,1),g(n);
for(int i=0;i<n;i ) cin>>v[i];
for(int i=0;i<n;i )
{
for(int j=0;j<i;j )
{
if(v[j]<v[i])
{
f[i]=max(f[i],f[j] 1);
}
}
}
int ret=0;
for(int i=0;i<n;i )
{
if(f[i]>ret)
ret=f[i];
}
cout<<ret<<endl;
return 0;
}如何获得最大子序列呢？ 我们用g数组保存最大数组开始转换的下标，
代码语言：javascript复制cpp#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> v(n),f(n,1),g(n);
for(int i=0;i<n;i ) cin>>v[i];
for(int i=0;i<n;i )
{
for(int j=0;j<i;j )
{
if(v[j]<v[i])
{
if(f[i]<f[j] 1)//记录子序列转换的位置
g[i]=j;
f[i]=max(f[i],f[j] 1);
}
}
}
int ret=0,k=0;
for(int i=0;i<n;i )
{
if(f[i]>ret)
{
ret=f[i];
k=i;
}
}
for(int i=0;i<ret;i )
{
cout<<v[k]<<' ';
k=g[k];//依次还原
}
cout<<endl;
cout<<ret<<endl;
return 0;
}最长公共子序列
问题描述：有两个字符串，选出它们公共的子串，并且该子串的长度最大。 问题解决：f[i][j]表示字符串1(str1)以i结尾，字符串2(str2)以j结尾的最大子串。 我们知道动态规划类题目都会用到上一次的结果，那么f[i][j]怎么用上一层计算的结果来计算呢? f[i][j]有这么几种分法：str1[i]==str2[j],那么f[i][j]=f[i-1][j-1] 1 str1[i]!=str2[j],这里就有3种情况： 1.i-1之前的子串与j之前的匹配 2.j-1之前的子串与i之前的子串匹配 3.i-1，j-1之前的子串匹配。 其中1，2两种情况包含了第3种情况。 f[i][j]=max(f[i-1][j],f[i][j-1]) 最后还需要把这两个绿的地方进行比较一下。因为有i-1的情况，所以都从1位置开始读入，开始匹配。
代码语言：javascript复制cpp#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string str1,str2;
while( cin>>str1>>str2)
{
str1.insert(str1.begin(), ' ');
str2.insert(str2.begin(), ' ');
vector<vector<int>> f(str1.size(),vector<int>(str2.size(),0));
for(int i=1;i<str1.size(); i)
{
for(int j=1;j<str2.size(); j)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(str1[i]==str2[j])
f[i][j]=max(f[i][j],f[i-1][j-1] 1);
}
}
cout<<f[str1.size()-1][str2.size()-1]<<endl;
}
return 0;
}
