Minimum Path Sum
Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
Note:You can only move either down or right at any point in time.
这个问题相当于寻宝问题Unique paths问题的加权版本。
每个格子的数字可以想象成为消耗的时间或者金钱,要寻找最佳路径,是的消耗最小。
连所有路径都能寻找到,还会怕找不到最优路径吗?呵呵。
不过要会利用动态规划法,从地往上逐步填表。
这里只使用一维表,如果使用二维表,会简单点。
注意填表不要填错了,下面注有向下走向右走的地方需要格外小心。
填写的时候要清楚,每个格子代表什么含义。
比如当前格子是table[i]; 那么table[i]代表下一行这个格(由下往上填表)的最优路径,如果是二维表就好理解点,比如当前格是table[r][i],那么我们就可以利用table[r+1][i]代表格子[r+1][i]的最优路径了。
table[i+1]代表往右一列这一格的最优路径。二维表表示:当前格是table[r][i], 那么table[r][i+1]代表格子[r][i+1]最优路径。
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
int r = grid.size();
if (r < 1) return 0;
int c = grid[0].size();
vector<int> table(c);
if (c-1>=0)
table[c-1] = grid[r-1][c-1];
for (int i = c-2; i >= 0; i--)
{
table[i] = table[i+1] + grid[r-1][i];
}
for (int i = r-2; i >= 0; i--)
{
//最后一列只能往下走了,所以特殊处理一下
table[c-1] += grid[i][c-1];
for (int j = c-2; j >=0; j--)
{
//向右走
if (table[j] <= table[j+1])
{
table[j] += grid[i][j];
}
//向下走
else table[j] = grid[i][j] + table[j+1];
}
}
return table[0];
}
};
12.23更新一个程序,利用哨兵大大简化程序,不过理解起来稍微难点:
int minPathSum3(vector<vector<int> > &grid)
{
int row = grid.size();
if (row < 1) return 0;
int col = grid[0].size();
//注意:一定需要初始化为INT_MAX,否则就需要额外处理;
vector<int> ta(col+1, INT_MAX);
ta[col-1] = 0;//作为第一个数的启动,必须选择第一个格
for(int i = row-1; i>=0; i--)
{
for (int j = col-1; j >= 0; j--)
{
int t = min(ta[j], ta[j+1]);
ta[j] = t + grid[i][j];
}
}
return ta[0];
}
//2014-2-8
int minPathSum(vector<vector<int> > &grid)
{
if (grid.empty() || grid[0].empty()) return 0;
//小心初始化好
int *A = new int[grid[0].size()+1];
A[0] = INT_MAX; A[1] = grid[0][0];
for (int i = 1; i < grid[0].size(); i++) A[i+1] = grid[0][i] + A[i];
for (int i = 1; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
A[j+1] = min(A[j], A[j+1]) + grid[i][j];
}
}
return A[grid[0].size()];
}
分享到:
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
Leetcode two sum java 解法
leetcode 2SUM 使用以前的地图最快的 2Sum O(N) 使用 unordered_map 比 map 快 以前的地图 là gì ? 上一张地图 đơn giản là 地图 nhưng thay vì ta cần một vòng for để khởi tạo 地图 thì ta khởi...
oj.leetcode题解, 2sum, 运用hashtable解决这到问题,时间复杂度O(N)
leetcode。 3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums 中是否有元素 a、b、c 使得 a + b + c = 0? 在数组中找到所有唯一的三元组,其总和为零。 示例输入: [-1, 0, 1, 2, -1...
3sum # Leetcode 解决方案以下是我在 Leetcode 上解决的一些问题,如果你喜欢/找到任何你的答案,请留下一个星。 如果你想与我联系,我在下面分享了我的 Linkedin URL。 问题 # 标题 # 解决方案 困难 1 二和 简单...
Leetcode 1 two sum C++ code
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number ...LeetCode ...Sum ...Sum ...Sum ...Minimum Path Sum 73
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating Characters LeetCode 13 Roman to ...
leetcode 轮廓 1_count_and_say.cpp - super_ugly_number.cpp - Detect_Pattern.cpp - degree_of_array.cpp - 键盘.cpp - 2Sum_Data_Structure_Design.cpp - shuffle_array.cpp - permutations.cpp - kth_missing_...
leetcode 2sum leetCode解决方案 我对 leetCode 问题的解决方案 已解决的练习列表: 简单的: 2sum - 带有未排序的数组; O(n) 复杂度; 花了~3ms 2sum - 使用排序数组; O(n) 复杂度 罗马转整数; O(n) 复杂度 合并...
Minimum Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-...
Leetcode\TwoSum\TwoSum.cs 问题: 业绩报告: 反转整数 代码: Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中...
Leetcode\3Sum(15).swift Leetcode\k 站内最便宜的飞行(787).swift Leetcode\combination sum(39).swift Leetcode\count number of team(1395).swift Leetcode\counting bits(338).swift Leetcode \find 数组中的...
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;