淘先锋技术网

首页 1 2 3 4 5 6 7

数字三角形问题

成绩10开启时间2020年03月24日 星期二 23:15
折扣0.8折扣时间2020年04月21日 星期二 23:55
允许迟交关闭时间2020年04月21日 星期二 23:55

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

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

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

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

 测试输入期待的输出时间限制内存限制额外进程
测试用例 1 
  1. 5↵
  2. 7↵
  3. 3 8↵
  4. 8 1 0 ↵
  5. 2 7 4 4↵
  6. 4 5 2 6 5↵
 
  1. 30↵
1秒64M0

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

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


1、分析

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

Ⅰ 最优子结构

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

Ⅱ 重叠子问题

上面已经分析过,题中一共有 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]

动态求解

已经分析过本题的最优子结构,由底层的最优解可以推出顶层的最优解,所以求解过程是自底向上的。采用一个二维数组 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])

当 i = n - 1 (初始情况): 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,做最扎实的程序员 ----

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

在这里插入图片描述