poj 1163

题目链接：http://poj.org/problem?id=1163

简单的动态规划问题，因为数据是三角形，所以用到了数组的压缩存储

假设数据用a[][]存储  dp[i][j]表示第i行第j个位置可以取到的最大值

动态规划dp[i][j]=max{dp[i-1][j],dp[i-1][j-1]}+a[i][j];

虽然节省了空间，但代码显然比预想的要乱

代码如下：

#include <stdio.h>
#include <stdlib.h>
short a[5100];
short dp[5100];
short pos1(int i,int j)
{
    return a[i*(i+1)/2+j];
}
short pos3(int i,int j)
{
    return dp[i*(i+1)/2+j];
}
void pos2(int i,int j,int k)
{
    dp[i*(i+1)/2+j]=k;
}
short max1(int i,int j)
{
    if(j==0)
    {
        return pos3(i-1,j);
    }
    else if(j==i)
    {
        return pos3(i-1,j-1);
    }
    else
    {
        return pos3(i-1,j)>pos3(i-1,j-1)?pos3(i-1,j):pos3(i-1,j-1);
    }
}
int main(int argc, char** argv) {

    int n,i,j,k=0,max=0;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        for(j=0;j<=i;++j)
        {
        scanf("%hd",&a[k++]);
        }
    }
    pos2(0,0,a[0]);
    for(i=1;i<n;++i)
    {
        for(j=0;j<=i;j++)
        {
            pos2(i,j,max1(i,j)+pos1(i,j));
        }
    }
    for(i=0;i<n;++i)
    {
        if(pos3(n-1,i)>max)
            max=pos3(n-1,i);
    }
    printf("%d\n",max);
    return (EXIT_SUCCESS);
}