[HDU] 2084 数塔 入门dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2084

方法：是对于每一个塔中第x行第y个位子的地方,设其所累加的最大和F(x,y)，当前位子本来就有的数字current(x,y)，当前位子处于的行的元素个数cx.则状态转移方程为：

　　　　　{

　　　　　　Max(F(x-1,y)+current(x,y),F(x-1,y-1)+current(x,y));

F(x,y) = 　1, x==1 and y==1;　

　　　　　　0, x<0 or y<0;

　　　　　}　　

 感想：简单题。

#include<iostream>
using namespace std;
int matrix[102][102];
int main()
{
    int test =0,c=0,n,inputTemp,result;
    cin>>test;
    while(c<test)
    { 
        result = 0;
        scanf("%d",&n);
        memset(matrix,0,sizeof(matrix));
        for(int i =1;i<=n;i++)
            for(int j =1;j<=i;j++)
                scanf("%d",&matrix[i][j]);
        for(int i =2;i<=n;i++)
            for(int j =1;j<=i;j++)
                matrix[i][j] += (matrix[i-1][j] > matrix[i-1][j-1] ? matrix[i-1][j] : matrix[i-1][j-1]);
        int max =0;
        for(int i =1;i<=n;i++)
            if(matrix[n][i]>max)
                max = matrix[n][i];
        cout<<max<<endl;
        c++;
    }
    return 0;
}