闫氏DP分析法
一、状态表示:f[i][j]所以
1. 集合:从最后一层到顶点(1, 1)的路径之和的方案(从底走到(i,j)的所有路径的集合)
2. 属性:最大值
二、状态计算:
1. 思想-----集合的划分
2. 集合划分依据:根据最后一步的来向, 即来自左下和来自右下两种.
三:代码:
include [HTML_REMOVED]
using namespace std;
const int N=510;
int f[N][N];
int main ()
{
int n; cin>>n;
for(int i=1;i<=n;i)
{
for(int j=1;j<=i;j)
{
cin>>f[i][j];
}
}
for(int i=n-1;i>0;i–)
for(int j=1;j<=i;j++)
f[i][j]+=max(f[i+1][j],f[i+1][j+1]);//分成两部分,从底到左的所有路径和,从底到右的所有路径和,加 上最上面的那个,即为最大的
cout<<f[1][1]<<endl;
return 0;
}
注释:最顶上的元素是(1,1)
这个题的关键是从底到上的遍历,可以少考虑边界问题。