摘要
Title: 898. 数字三角形
Tag: dp、数字三角形模型
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

898. 数字三角形

• 题意

  给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

• 思路

  从下向上dp，除了最后一层，每一个点由左下方和右下方走来，最后输出$dp[1][1]$即可，代表(1, 1)的最大路径和

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-06 16:40:50
  FilePath: \ACM\Acwing\898.py
  LastEditTime: 2022-03-06 16:44:20
  '''
  N = 510
  
  dp = [[0] * N for _ in range(N)]
  
  n = int(input())
  for i in range(1, n + 1):
      dp[i][1:] = map(int, input().split())
  
  for i in range(n - 1, 0, -1):
      for j in range(1, i + 1):
          dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1])
  
  print(dp[1][1])