入门DP | 1：数字三角形问题

迷南。 2023-05-28 11:14 62阅读 0赞

# 数字三角形问题 #

问题描述: 给定一个有n行数字组成的数字三角形. 试设计一个算法, 计算出从三角形的顶至底的一条路径, 使该路径经过的数字和最大.

算法设计: 对于给定的n行数字组成的三角形, 计算从三角形顶至底的路径经过的数字和的最大值.

数据输入: 第1行数字三角形的行数n, 1<=n<=100. 接下来n行是数字三角形各行中的数字. 所有数字在0~99之间.

结果输出: 第1行中的数是计算出的最大值.

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入</th> 
   <th>期待的输出</th> 
   <th>时间限制</th> 
   <th>内存限制</th> 
   <th>额外进程</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td>&nbsp; 
    <ol> 
     <li>5↵</li> 
     <li>7↵</li> 
     <li>3&nbsp;8↵</li> 
     <li>8&nbsp;1&nbsp;0&nbsp;↵</li> 
     <li>2&nbsp;7&nbsp;4&nbsp;4↵</li> 
     <li>4&nbsp;5&nbsp;2&nbsp;6&nbsp;5↵</li> 
    </ol></td> 
   <td>&nbsp; 
    <ol> 
     <li>30↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

--------------------

题意很好理解：在一个数字三角形中，从顶端到底端，选择一条元素和最大的路径。（每次只可选择当前位置左下/右下的元素）下图是对测试用例的图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

简单粗暴的思考一下：若用暴力枚举，从顶层到底层一共有 n-1 次选择，每次供选择的情况为2种，那么一共有 ![2^\{n-1\}][2_n-1] 条路径。一一计算和再选取最大值，时间复杂度为 ![O(2^n)][O_2_n] ，oh，糟糕的指数时间 ┭┮﹏┭┮。

--------------------

### 1、分析 ###

此题很明显是一个**典型的动态规划问题**，因为其满足动态规划的两大特性：

**Ⅰ 最优子结构**

从顶层到最底层的最优（和最大）路径中，期间任意一个元素到最底层的路径都是最优的。那么我们可以从底层往上推，得出顶层的最优路径。比如说，已知第二层的最优路径，我们求顶层的最优路径，就是选取第二层中3或8的更优路径和 + 7。所以，我们可以将底层的最优路径看作上一层的子问题，下一层的最优路径已知，那么上一层的最优路径就很容易推出。

**Ⅱ 重叠子问题**

上面已经分析过，题中一共有 ![2^\{n-1\}][2_n-1] 条路径，且每条路径中会有子问题重叠。比如：7-3-1-7-5 与 7-3-8-7-5 中，倒数第二层到底层的的子路径 7-5是重叠的。这也是为什么要用动态规划而不用分治法求解的根源。

--------------------

### 2、建模 ###

**数据的存储**

图中是一个规整的等腰三角形，那么我们储存在程序中应该采用二维数组的对应存储。下图显示的是一个简单的分支部分应该对应在数组中的储存方式。我们将三角形每一行对应于数组的一维下标：i = 0..n-1，将每一列对应于数组的二维下标：j = 0..i。在数字三角形中每次路径的选择可以选择左下/右下，对应在数组中，**在元素 a\[i\]\[j\] 处的选择应该是 a\[i+1\]\[j\] 或 a\[i+1\]\[j+1\]**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1][]

**动态求解**

已经分析过本题的最优子结构，由底层的最优解可以推出顶层的最优解，所以求解过程是**自底向上**的。采用一个二维数组 dp\[i\]\[j\] 来储存 a\[i\]\[j\] 元素到最底层的最优路径值。那么很容易列出状态转移方程：

当 i > n-1 : ![dp\[i\]\[j\] = a\[i\]\[j\] + max(dp\[i+1\]\[j\] , dp\[i+1\]\[j+1\])][dp_i_j_ _ a_i_j_ _ max_dp_i_1_j_ _ dp_i_1_j_1]

当 i = n - 1 （初始情况）: ![dp\[i\]\[j\] = a\[i\]\[j\]][dp_i_j_ _ a_i_j]

--------------------

### 3、代码实现  ###

直接附上AC代码

#include <cstdio>
    #include <algorithm>
    using namespace std;
    #define MAXN 105
    
    int main() {
        int n;
        scanf("%d", &n);
        int a[MAXN][MAXN], dp[MAXN][MAXN];
    
        /* 处理输入的数字三角形 */
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++) {
                scanf("%d", &a[i][j]);
                dp[i][j] = a[i][j];  //初始化dp数组
            }
    
        /* 自底向上的求解过程 */
        for (int i = n - 2; i >= 0; i--)  //从 n-2 ~ 0 层
            for (int j = 0; j <= i; j++)
                dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);  //选取下一层的最优解 + 本元素值
        printf("%d\n", dp[0][0]);  //输出结果
    }

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/753adf9cb9a34ab48043d862db13340d.png
[2_n-1]: https://private.codecogs.com/gif.latex?2%5E%7Bn-1%7D
[O_2_n]: https://private.codecogs.com/gif.latex?O%282%5En%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/dc1bbade9e064bbcaf7b86bbf00f51cb.png
[dp_i_j_ _ a_i_j_ _ max_dp_i_1_j_ _ dp_i_1_j_1]: https://private.codecogs.com/gif.latex?%5Cinline%20dp%5Bi%5D%5Bj%5D%20%3D%20a%5Bi%5D%5Bj%5D%20&plus;%20max%28dp%5Bi&plus;1%5D%5Bj%5D%20%2C%20dp%5Bi&plus;1%5D%5Bj&plus;1%5D%29
[dp_i_j_ _ a_i_j]: https://private.codecogs.com/gif.latex?%5Cinline%20dp%5Bi%5D%5Bj%5D%20%3D%20a%5Bi%5D%5Bj%5D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 2]: /images/20230528/080767b3933f4e77916c7c1f4fd5340f.png