The Triangle POJ - 1163 (动态规划经典入门题)

刺骨的言语ヽ痛彻心扉 2022-04-23 15:16 185阅读 0赞

7
    3   8
    8   1   0
    2   7   4   4
    4   5   2   6   5
    
    (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output

Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

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

Sample Output

30

解题思路:

最最最经典的动态规划入门题

初始状态是最后一层的数据,状态转移为一个结点左下方和右下方较大的那个加上结点值

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 110;
    //输入数字
    int N;
    int triArr[MAXN][MAXN];
    int stDp[MAXN][MAXN];
    
    int main() {
    	cin >> N;
    	for (int i = 0; i < N; ++i) {
    		for (int j = 0; j <= i; ++j) {
    			cin >> triArr[i][j];   //输入结果
    		}
    	}
    
    	//先把第一阶段的结果进行填充
    	for (int k = 0; k < N; ++k) {
    		stDp[N - 1][k] = triArr[N - 1][k];  //填充的结果是最后一行
    	}
    
    	for (int i = N - 2; i >= 0; --i) {
    		for (int j = 0; j <= i; ++j) {
    			stDp[i][j] = max(stDp[i+1][j], stDp[i+1][j + 1]) + triArr[i][j];
    		}
    	}
    	cout << stDp[0][0] << endl;
    
    	system("PAUSE");
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM学习-POJ-1163-The Triangle

菜鸟学习ACM，纪录自己成长过程中的点滴。学习的路上，与君共勉。 ACM学习-POJ-1163-The Triangle <table style="font-wei

桃扇骨/ 2022年09月17日 06:24/ 0 赞/ 173 阅读

相关 POJ1163DP

题意和解析，看代码最后部分 include <iostream> include <cstdio> include <cmath> using

淡淡的烟草味﹌/ 2022年08月18日 00:40/ 0 赞/ 34 阅读

相关 poj1742 动态规划经典多重背包

有n种不同面值的硬币，面值各为A1,A2,A3。。AN，数量各为C1,C2,C3,,,,,CN。给定数m，问这些硬币能组成小于等于m的数中的哪些数，输出这些数的数目。

梦里梦外;/ 2022年08月03日 08:22/ 0 赞/ 199 阅读

相关 POJ 3176-Cow Bowling/POJ 1163-The Triangle（简单DP-数塔）

Cow Bowling <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

冷不防/ 2022年07月12日 13:28/ 0 赞/ 148 阅读

相关 poj1163

include <iostream> include <algorithm> using namespace std;

曾经终败给现在/ 2022年06月18日 04:20/ 0 赞/ 204 阅读

相关合并石子（动态规划经典题）

步骤： 1. 设状态：f\[i\]\[j\]表示从第i堆合并到第j堆，合并成一堆的最小得分 2. 初始状态：f\[i\]\[i\]=0; 最终状态：f\[1\]\[n\]

太过爱你忘了你带给我的痛/ 2022年06月11日 08:14/ 0 赞/ 404 阅读

相关 POJ 1163 The Triangle

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

素颜马尾好姑娘i/ 2022年06月10日 12:44/ 0 赞/ 161 阅读

相关复制书稿（动态规划经典题）

Problem Description 现在要把m本有顺序的书分给k个人复制(抄写)，每一个人的抄写速度都一样，一本书不允许给两个(或以上)的人抄写，分给每一个人的书，必须

水深无声/ 2022年06月10日 10:06/ 0 赞/ 220 阅读

相关 The Triangle POJ - 1163 (动态规划经典入门题)

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

刺骨的言语ヽ痛彻心扉/ 2022年04月23日 15:16/ 0 赞/ 186 阅读

相关 [leetcode]动态规划之Triangle

动态规划之Triangle 题目思考答案题目 [leetcode入口][leetcode] 思考刚开始想这道题，想着的是建立一维

缺乏、安全感/ 2021年09月28日 14:46/ 0 赞/ 548 阅读