数字三角形问题

Description

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

解题思路:
    将原题数据如下编码:
    7(1,1)    
    3(2,1) 8(2,2)
    8(3,1) 1(3,2) 0(3,3) 
    2(4,1) 7(4,2) 4(4,3) 4(4,4)
    4(5,1) 5(5,2) 2(5,3) 6(5,4) 5(5,5)

    1、把当前(i,j)看成一个状态
    2、定义状态的指标函数dp(i,j)为从(i,j)出发时能得到的最大和(包括dp(i,j)本身的值)。
       (1)从(i,j)出发有2种决策,即向左,向右,如果向左走,需要先知道(i+1,j)出发后的最大和,即dp(i+1,j),如果向右走,需要先知道(i+1,j+1)出发后的最
       大和,状态转移方程为:dp(i,j)=dp(i,j)+max(dp(i+1,j),dp(i+1,j+1))
       (2)原问题即可抽象为填下面格子的问题 (绿色为已知数,依次填充与其平行的每一行)
                                       (5,5)
                               (5,4)(4,4)
                       (5,3)(4,3)(3,3)
               (5,2)(4,2)(3,2)(2,2)
       (5,1)(4,1)(3,1)(2,1)(1,1)

3、原问题的解即为dp(1,1)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; 

int dp[105][105];

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数字三角形问题 动态规划

    OJ 问题:Triangle(参见 http://poj.org/problem?id=1163)

    一只胡说八道的猴子
  • 数字三角形问题 动态规划

    OJ 问题:Triangle(参见 http://poj.org/problem?id=1163) 题意:在数字三角形上寻找一条沿相邻顶点从顶到底走的路径,使...

    一只胡说八道的猴子
  • [动态规划] 数字三角形问题(一维数组实现)

    一个数字三角宝塔。设数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下走。假设三角形行数小于等于100编程求解...

    孟君
  • 做题总结——数字三角形

    先介绍一种解法。这道题目可以利用“杨辉三角”的思路,根据一个上面的元素与下面两个元素的递推公式(在动态规划里面称作状态转移方程),从下至上地解决此问题(详细思路...

    用户8224910
  • 1220 数字三角形

    1220 数字三角形  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descripti...

    attack
  • DP专题 | 数字三角形 - POJ 1163

    从本篇开始,准备做一系列的专题讲解,主要参考《算法竞赛入门经典》、《算法竞赛进阶指南》两本书。主要是为了能够更加系统的讲解各个知识点,这两本书已经讲得很好了,建...

    ACM算法日常
  • 2189 数字三角形W

    2189 数字三角形W 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 数字三角...

    attack
  • POJ 1163(数字三角形)

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

    AI那点小事
  • P1216 [USACO1.5]数字三角形 Number Triangles

    题目描述 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 ...

    attack
  • python写个三角形的问题

    *              *****       **             ****

    py3study
  • P1118 [USACO06FEB]数字三角形Backward Digit Su…

    题目描述 FJ and his cows enjoy playing a mental game. They write down the numbers fr...

    attack
  • 算法训练 数字三角形

    问题描述   (图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路   径,使该路径所经过的数字的总和最大。   ●每一步...

    AI那点小事
  • 符号三角形问题-回溯法

    问题描述:   由14个“+”号和14个“-”号组成的符号三角形。   2个同号下面是“+”号,2个异号下面是“-”号。 如图:  +   +   _   +...

    用户1154259
  • C#版 - Leetcode611.有效三角形的个数 - 题解

    在线提交: https://leetcode-cn.com/problems/valid-triangle-number/

    Enjoy233
  • HDUOJ---三角形(组合数学)

    http://acm.hdu.edu.cn/showproblem.php?pid=1249 三角形 Time Limit: 2000/1000 MS (Ja...

    Gxjun
  • OJ刷题记录:杨辉三角形

    题目描述: 杨辉三角形又称Pascal三角形,它的第i+1行是(a+b)i的展开式的系数。

    英雄爱吃土豆片
  • 图解两数之和的变形题之「有效三角形的个数」

    题目要求选出三条边,使得这三条边能够构成三角形,咋眼看上去这道题貌似和 TwoSum 没啥关系。

    五分钟学算法
  • 611. 有效三角形的个数

    CaesarChang张旭
  • 【leetcode刷题】T214-最大三角形面积

    https://leetcode-cn.com/problems/largest-triangle-area/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券