算法十六：数字三角形

深藏阁楼爱情的钟 2022-05-21 07:52 180阅读 0赞

**时间限制：**2 sec

**空间限制：**256 MB

### **问题描述** ###

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

![0fff125f250ff846c2c8d5898b074eda44617600.png][]

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

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

### **输入格式** ###

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

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

### **输出格式** ###

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

### **样例输入** ###

2 3

4 5 6

7 8 9 10

### **样例输出** ###

### **样例解释** ###

不停地向右下走即可。

### **提示** ###

\[如果我们使用搜索算法，我们会在搜索时记录哪些信息呢？\]

\[当前到达的点的坐标、当前经过路径上数的总和！\]

\[总和显然是越大越好！\]

\[于是可以设计出状态：dp\[i\]\[j\] 表示走到坐标为 (i,j) 的点时的最大总和。\]

\[很容易就可以设计出状态转移方程啦！\]

###  ###

### **一. 伪代码** ###

![70][]

### **二. 具体实现（C++）** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
//dp:用于动态规划的数组，d\[i\]\[j\]表示要走到第i行第j列能得到最大数字总和  
vector<vector<int>> dp;  
// 本函数计算答案（最大经过位置数字总和）  
// n：描述数字三角形大小，意义同题目描述  
// a：描述整个数字三角形，第 i 行的第 j 个数存放在 a\[i\]\[j\]  
// 中（你需要特别注意的是，所有下标均从 1 开始，也就是说下标为 0 的位置将存放无效信息）  
// 返回值：最大经过位置数字总和  
int getAnswer(int n, vector<vector<int>> a) \{  
dp.resize(n+1);  
for(int i=0; i<=n; ++i)  
dp\[i\].resize(i+2);  
for(int i = 1; i <= n; ++i)  
for(int j = 1; j<=i; ++j)  
dp\[i\]\[j\] = max(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\])+a\[i\]\[j\];//用左上角和正上方的dp值更新  
int ans = 0;  
for(int i=1; i<=n; ++i)  
ans = max(ans, dp\[n\]\[i\]);//求最大的数字之和  
return ans;  
\}  
// ================= 代码实现结束 =================

[0fff125f250ff846c2c8d5898b074eda44617600.png]: /images/20220521/081954f8960e4fbf95bef8f819ec63e2.png
[70]: /images/20220521/684fd08e0a8743d8b7b992f77e10df59.png