欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Triangle Leetcode #120 题解[C++]

程序员文章站 2022-06-03 10:37:09
...

题目来源


https://leetcode.com/problems/triangle/

题目描述


Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

题意大致是给出一个类似杨辉三角结构的二维数组, 但每个位置上的数值是随机的. 要求给出一条自顶向下的通路, 其中该通路的SUM为路上途经的各点的值之和, 要求通路的SUM最小. 从上往下走时, 要求只能走下一层与该点相邻的两个顶点.

具体参照英文说明中给出的样例.

解题思路


这道题一开始我的思路又出了偏差. 我开始的想法是用一种类似贪心的策略.

从最后一层开始往上走. 维护一个大小等于最后一层的数组作为result, 表示起点有这些.
因此, 从倒数第二层开始自底向上遍历所有层. 每一次遍历都嵌套一次内层遍历去遍历当前层的所有顶点.

对于当前层的正好被遍历到的某个顶点i, 查看它在上一层的两个(或是一个)相邻顶点, 选择一个较小的加入到顶点i构成的路径(对应result数组中的某个值)中.

两层遍历都完成后, 数组result的最小值即是结果.

但以上的方法实现之后却总是Wrong Answer. 仔细思考后发现这种方法其实是不正确的. 比方说在下面的triangle中, 所有的路径都因为先前的”眼前的小便宜”失去了走三角形中间权极小(-9)的一个点的机会.
Triangle Leetcode #120 题解[C++]

后来参考了讨论区的代码, 有了正确的动态规划的思路.
核心方程如下:

从层 j 中点 i 往下走的路径最小和 = min (从层 j+1 中点 i 往下走的最小路径和, 从层 j+1 中点 i+1 往下走的最小路径和 ) + triangle[j][i]

它的正确性是很显然的.

细节如下.

  • 1 新建一个等于triangle最后一排的数组result
  • 2 从倒数第二层开始自底向上遍历每一层,
    • 2.1 遍历数组result中的前n个数, n的大小等于当前层 j 的大小
    • 2.2 对于当前下标为i, result[i]=min(result[i],result[i+1])+triangle[j][i];
  • 3 返回result[0]

上面的伪代码本质上是一个动态规划. 具体的解释是这样的, 对于当前所处的每一层 j 和层中的第 i 个数, result[i] 和result[i+1] 其实表示了在下一层中与本层的数 i 相邻的那两个数分别对应的路径加权.

(比方说result[i+1]就表示了从triangle[j+1][i]开始往下走, 所能取到的路径和最小的一条路—–就是从该点出发往下走的一条最优的路的路上各点之和)

因此, 很显然地, result[i]=min(result[i],result[i+1])+triangle[j][i]就表示了从triangle[j][i]点开始往下走, 所能走的最优的路的路上各点之和.

通过不断对result[i]进行刷新, 最后当 j = 0, 也就是遍历完的时候, result[0]就表示了从顶点往下走, 所能走的路上各点之和最小的一条路—–这条路上的各点之和.

代码实现


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> result = triangle.back();
        for (int count = 2; count <= triangle.size(); count++) {
            int currentRow = triangle.size() - count;
            for (int index = 0; index <=currentRow; index++) {
                result[index] = min(result[index],result[index+1]) + triangle[currentRow][index];
            }
        }
        return result[0];

    }
};

Triangle Leetcode #120 题解[C++]

相关标签: Algorithm