首页 > 代码库 > HDU -- 2084 数塔(简单DP)

HDU -- 2084 数塔(简单DP)

    HDU -- 2084  数塔

题意:

    自上而下,选择一条累计和最大的路径

分析:

    顶点只与左右两个子节点相关,且子节点路径的选择与顶点无关(无后效性)

    状态dp[i][j]:表示(i,j)点向下得到的最大累计和

    转移方程:

            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + v[i][j];



核心:

     for(i = n; i>=1; i--)    
    {
        for(j = 1; j<=i; j++)
        {
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + v[i][j];
        }
    }


代码:

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <time.h>

using namespace std;

int v[100+10][100+10];
int dp[100+10][100+10];

int main()
{
	freopen("a.txt", "r", stdin);

	int t, n, i, j;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		for(i = 1; i<=n; i++)
		{
			for(j = 1; j<=i; j++)
			{
				scanf("%d", &v[i][j]);
			}
		}
		memset(dp, 0, sizeof(dp));
		for(i = n; i>=1; i--)
		{
			for(j = 1; j<=i; j++)
			{
				dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + v[i][j];
			}
		}
		printf("%d\n", dp[1][1]);
	}
	return 0;
}