算法训练营 -- 数字三角形

问题描述

给定一个高度为 n 的“数字三角形”，其中第 i 行（1<=i<=n）有 i 个数。（例子如下图所示）

1
2 3
4 5 6
7 8 9 10

初始时，你站在“数字三角形”的顶部，即第一行的唯一一个数上。每次移动，你可以选择移动到当前位置正下方或者当前位置右下方的位置上。即如果你在 (i,j)（表示你在第i行从左往右数第j个数上，下同），你可以选择移动到 (i+1,j) 或 (i+1,j+1)。

你想让你经过的所有位置（包括起点和终点）的数字总和最大。求这个最大值。

输入格式

第一行一个正整数 n，表示数字三角形的大小。

第 2 行到第 n+1 行，第 i+1 行为 i 个用空格隔开的非负整数，描述数字三角形的第 i 行。

输出格式

一行一个整数，表示经过路径上数的最大总和。

样例输入

4

1

2  3

4  5  6

7  8  9  10

样例输出

20

样例解释

不停地向右下走即可。

提示

• 如果我们使用搜索算法，我们会在搜索时记录哪些信息呢？
• 当前到达的点的坐标、当前经过路径上数的总和！
• 总和显然是越大越好！
• 于是可以设计出状态：dp[i][j] 表示走到坐标为 (i,j) 的点时的最大总和。
• 很容易就可以设计出状态转移方程啦！

题解

这是动态规划入门题。思路分析：

1. 如要走进某个点，那么根据题意，只有正上方和左上方可以走！
2. 故，是不是可以求出走到某点a(i, j) 的最大值呢？
3. 所以可以列式：d(i, j) = max{ d(i-1, j-1), d(i-1, j)} + a(i, j)

代码实现

#!/usr/bin/env pypy3
# encoding: utf-8

# ================= 代码实现开始 =================

# 本函数计算答案（最大经过位置数字总和）
# n：描述数字三角形大小，意义同题目描述
# a：描述整个数字三角形，第 i 行的第 j 个数存放在 a[i][j]
# 中（你需要特别注意的是，所有下标均从 1 开始，也就是说下标为 0 的位置将存放无效信息）
# 返回值：最大经过位置数字总和
def getAnswer(n, a):
    #dp是用于动态规划的数组。dp[i][j]表示要走到第i行第j列能得到最大数字之和
    dp = [[0 for j in range(i + 2)] for i in range(n+1)]

    dp[1][0] = dp[1][2] = 0
    dp[1][1] = a[1][1]
    for i in range(2, n + 1):
        dp[i][0] = dp[i][i + 1] = 0
        for j in range(1, i + 1):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
            # 用左上角和正上访的dp值更新
    ans = 0
    for i in range(1, n+1):
        ans = max(ans, dp[n][i])
    
    return ans

# ================= 代码实现结束 =================
if __name__ == '__main__':
    n = eval(input())
    a = [[] for i in range(n + 1)]
    for i in range(1, n + 1):
        a[i] = list(map(int, input().split()))
        a[i].insert(0, 0)
    print(getAnswer(n, a))