数字三角形

如图所示，一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。 　每一步可沿左斜线向下或右斜线向下走；

1< 三角形行数< 25； 　三角形中的数字为整数< 1000；

输入

第一行为N，表示有N行 后面N行表示三角形每条路的路径权

输出

路径所经过的数字的总和最大的答案

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30

#include<bits/stdc++.h>
using namespace std;
int n,a[30][30],s;
int v[30][30];
int dfs(int x,int y)
	{
	if(x==n)
	{
        return a[x][y];
    }
	else{
        if(v[x][y]!=-1)
		{
        	return v[x][y];
		} 
        else{
            v[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
            return v[x][y]; 
        }   
    }
}
int main(){ 
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
			v[i][j]=-1;
		}
	}
	;
	cout<<dfs(1,1);
	return 0;
}