[数据结构与算法]P1216 数字三角形——动态规划 7.30

#include<stdio.h>

int max(int a,int b) {? //计算a,b两数中最大值
if(a>b)
return a;
else
return b;
}

int main() {
int i,j,N;
scanf("%d",&N);
int a[N][N]={-100};? //用以保存金字塔中的数?
int dp[N][N]={0};? ?//保存最大路径和
for(i=0;i<N;i++)
? ? for(j=0;j<=i;j++)
? ? ? ? scanf("%d",&a[i][j]); //将金字塔的数输入a数组
dp[0][0]=a[0][0];?
for(i=1;i<N;i++)? //将a数组第一列的最大路径和赋值给dp数组
? ? dp[i][0]=a[i][0]+dp[i-1][0];

for(i=1;i<N;i++) //将数组a的对角线的最大路径和赋值给dp
? ? for(j=1;j<=i;j++)
? ? ? ? if(j==i)
? ? ? ? dp[i][j]=a[i][j]+dp[i-1][j-1];

for(i=2;i<N;i++)
? ? for(j=1;j<i;j++)
? ? ? ? dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];? //状态转移方程

int max=0;
for(j=0;j<N;j++)
if(dp[N-1][j]>max)
? ? max=dp[N-1][j];
printf("%d",max);
return 0;
}

数组a中的移动方向只能向下和斜向下

解法二（选自洛谷题解）：

该算法思路为逆向求解：由下至上最终求出最大路径。

include<iostream> 
include<cstdio> 
include<cmath> 
using namespace std;  
int n;  
int a[1000][1000];  
int main()  
{       
	scanf("%d",&n);  
	for(int i=0;i<n;i++)  
	for(int j=0;j<=i;j++)  
	scanf("%d",&a[i][j]);//以上输入  
	for(int i=n-2;i>=0;i--)   
	{  
 		for(int j=0;j<=i;j++)//for循环按顺序扫描除最后一排前的所有数  
		a[i][j]+=max(a[i+1][j],a[i+1][j+1]); 
        //从左下，右下中选取大的加到现在的位置上 
    } 
    cout<<a[0][0]<<endl; 
    return 0; 
 }