博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Triangle 三角形
阅读量:5825 次
发布时间:2019-06-18

本文共 2044 字,大约阅读时间需要 6 分钟。

 

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).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 

这道题和非常的类似,都是用动态规划Dynamic Programming来求解的问题。而且递推式也比较容易看出来,我最先想到的方法是:

从第二行开始,triangle[i][j] = min(triangle[i - 1][j - 1], triangle[i - 1][j]), 然后两边的数字直接赋值上一行的边界值,由于限制了空间复杂度,所以我干脆直接就更新triangle数组,代码如下:

 

class Solution {public:    int minimumTotal(vector
> &triangle) { int n = triangle.size(); for (int i = 1; i < n; ++i) { for (int j = 0; j < triangle[i].size(); ++j) { if (j == 0) triangle[i][j] += triangle[i - 1][j]; else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i - 1][j - 1]; else { triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } } } int res = triangle[n - 1][0]; for (int i = 0; i < triangle[n - 1].size(); ++i) { res = min(res, triangle[n - 1][i]); } return res; }};

 

这种方法可以通过OJ,但是毕竟修改了原始数组triangle,并不是很理想的方法。在网上搜到一种更好的DP方法,这种方法复制了三角形最后一行,作为用来更新的一位数组。然后逐个遍历这个DP数组,对于每个数字,和它之后的元素比较选择较小的再加上上面一行相邻位置的元素做为新的元素,然后一层一层的向上扫描,整个过程和冒泡排序的原理差不多,最后最小的元素都冒到前面,第一个元素即为所求。代码如下:

 

class Solution {public:    int minimumTotal(vector
> &triangle) { int n = triangle.size(); vector
dp(triangle.back()); for (int i = n - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]; } } return dp[0]; }};

 

下面我们来看一个例子,对于输入数组:

     -1

    2   3

  1  -1  -3

5   3   -1   2

下面我们来看DP数组的变换过程。

DP:5  3  -1  2

DP:4  3  -1  2

DP:4  -2  -1  2

DP:4  -2  -4  2

DP:0  -2  -4  2

DP:0  -1  -4  2

DP:-2  -1  -4  2

 

转载地址:http://saidx.baihongyu.com/

你可能感兴趣的文章
OllyDBG 入门系列教学--让你瞬间成为破解高手
查看>>
jQuery插件开发的准备
查看>>
Dubbo点滴(2)之集群容错
查看>>
Zend Framework 自动加载类的实现方法
查看>>
7月24日云栖精选夜读:未来的超级智能网络攻击需要AI竞技俱乐部来拯救
查看>>
Cloudera携手CenturyLink提供大数据即服务
查看>>
所有代码都需要单元测试覆盖吗?
查看>>
如何创建线程
查看>>
Eclipse搭建Android ADT+SDK+AVD
查看>>
《Android传感器开发与智能设备案例实战》——第2章,第2.1节安装Android SDK的系统要求...
查看>>
《树莓派Python编程入门与实战(第2版)》——3.8 使用适当的工具
查看>>
《Python游戏编程入门》——导读
查看>>
《软件工程(第4版?修订版)》—第1章1.11节本章对单个开发人员的意义
查看>>
Java IO: RandomAccessFile
查看>>
桌面数据库绿色版
查看>>
android 国内工具集
查看>>
建筑效果图素材站SKALGUBBAR
查看>>
python gzip 压缩/解压缩 字符串
查看>>
Android framework系统默认设置修改
查看>>
android staticlayout使用讲解
查看>>