数塔 HDU - 2084【动态规划】题解

妖狐艹你老母 2021-07-25 02:43 412阅读 0赞

### 题解目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?  
Input  
输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间\[0,99\]内。  
Output  
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。  
Sample Input

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

Sample Output  
30

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e2 + 10;
    int dp[maxn][maxn];  表示走到dp[i][j]的最大和
    int a[maxn][maxn];
    int main()
    { 
    	int T;
    	cin >> T;
    	while (T--)
    	{ 
    		int n;
    		cin >> n;
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= i; j++)
    				cin >> a[i][j];
    		for (int i = 1; i <= n; i++)
    		{ 
    			dp[n][i] = a[n][i];  /初始值
    		}
    		for (int i = n-1; i >= 1; i--)
    		{ 
    			for (int j = 1; j <= i; j++)
    			{ 
    				dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j]; 状态转移方程
    			}
    		}
    		cout << dp[1][1] << endl;
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/c2a0d3522d9547be99f052f5a249a5f7.png