找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2330|回复: 12
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Minimum Path Sum】-【刷题第一弹2014】

[复制链接]

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
发表于 9-30-2014 07:37 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 wyu277 于 9-30-2014 07:38 PM 编辑

Leetcode传送门:
Minimum Path Sum

题目:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)

===============
点此查看汇总贴
===============

本帖被以下淘专辑推荐:

18

主题

11

精华

478

积分

高级会员

Rank: 3Rank: 3

积分
478
 楼主| 发表于 9-30-2014 07:56 PM | 显示全部楼层
本帖最后由 wyu277 于 9-30-2014 07:58 PM 编辑

思路:
简单的Dynamic Programming, Path只可能从左边和上面2条路选。opt(i,j) = min(opt(i,j-1),opt(i-1,j)) + m[j]
(opt(i,j) 代表从起始点到m[j]的最短路径,i 代表行,j 代表列)

base cases:
第一行的时候,只有左边一条路可以选。
所以,(i==0) opt(i,j) = opt(i,j-1) + m[j]

每行,第一个元素的时候,也只有一条路,上面一条路。
(j==0) opt(i,j) = opt(i-1,j) + m[j]

代码:

  1. public int minPathSum(int[][] grid) {
  2.     if (grid==null||grid.length==0) return 0;
  3.    
  4.     int[][] f= new int[grid.length][grid[0].length];
  5.    
  6.     for (int j=0;j<grid[0].length;j++)
  7.         if (j==0)   
  8.             f[0][j] = grid[0][j];
  9.         else f[0][j] = f[0][j-1]+grid[0][j];
  10.         
  11.     for (int i=1;i<grid.length;i++)
  12.         for (int j=0;j<grid[0].length;j++) {
  13.             if (j==0)
  14.                 f[i][j] = f[i-1][j] + grid[i][j];
  15.             else f[i][j] = grid[i][j] + Math.min(f[i-1][j],f[i][j-1]);
  16.         }
  17.         
  18.     return f[grid.length-1][grid[0].length-1];
  19. }
复制代码

复杂度分析:
Time Complexity: O(n^2)
Space Complexity: O(n^2)

当然,上面是2维的DP。鉴于optimal公式,当前最优解只跟上一行同列 和 同行前一列有关。可以继续简化为一维的。

代码

  1. public int minPathSum(int[][] grid) {
  2.     if (grid==null||grid.length==0) return 0;
  3.    
  4.     int[] f= new int[grid[0].length];
  5.    
  6.     for (int j=0;j<grid[0].length;j++)
  7.         if (j==0)   
  8.             f[j] = grid[0][j];
  9.         else f[j] = f[j-1]+grid[0][j];
  10.         
  11.     for (int i=1;i<grid.length;i++)
  12.         for (int j=0;j<grid[0].length;j++) {
  13.             if (j==0)
  14.                 f[j] += grid[i][j];
  15.             else f[j] = grid[i][j] + Math.min(f[j],f[j-1]);
  16.         }
  17.         
  18.     return f[grid[0].length-1];
  19. }
复制代码


细节:
这题的细节我觉得只在于base cases上。

相似题目:
回复 支持 反对

使用道具 举报

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 10-24-2014 02:58 PM | 显示全部楼层
  1. public class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         if(grid == null || grid.length == 0)
  4.             return 0;
  5.         int m = grid.length;
  6.         int n = grid[0].length;
  7.         int[] array = new int[n];
  8.         for(int i = 0; i < n; i++){
  9.             if(i == 0)
  10.                 array[i] = grid[0][i];
  11.             else
  12.                 array[i] = grid[0][i] + array[i-1];
  13.         }
  14.         for(int i=1; i<m; i++){
  15.             for(int j=0; j<n ;j++){
  16.                 if(j == 0)
  17.                     array[j] += grid[i][j];
  18.                 else{
  19.                     array[j] = grid[i][j] + Math.min(array[j], array[j-1]);
  20.                 }
  21.             }
  22.         }
  23.         return array[n-1];
  24.     }
  25. }
  26. 一维DP,只要维护一个一维的数组就好了,time O(n*m),space O(n)
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表