s**********r 发帖数: 8153 | 1 怎么做阿?我只会用2-d array做,忽然看见人家1-d的做的非常好。
可是没看懂阿,怎么用滚动数组阿? |
r**h 发帖数: 1288 | 2 因为当前行的值只和上一行有关,所以用
c[n%2]表示当前行,c[1-n%2]表示上一行即可 |
s**********r 发帖数: 8153 | 3 这就更不明白了。当前的值应该和下一行和右边都有关阿。不是可以向右和下边走么?
【在 r**h 的大作中提到】 : 因为当前行的值只和上一行有关,所以用 : c[n%2]表示当前行,c[1-n%2]表示上一行即可
|
r**h 发帖数: 1288 | 4 抱歉我看错题了。。
这题你把矩阵转45度,就可以转化成按层计算了呀
比如说
1 2 5
3 4 6
转化成
1
3 2
4 5
6
找一个从1到6得到path,然后就可以应用那个方法了
能分享一下用一维矩阵的代码吗? |
s**********r 发帖数: 8153 | 5 阿?你这个方法我越说越糊涂了。
到处用的都是1维的,2维dp的人家都不稀罕用了。。。我只能想到二维的。
你这个我更不明白怎么做了,啥意思阿
http://discuss.leetcode.com/questions/240/minimum-path-sum
这里边不全是一维的么。。。
神马意思?
【在 r**h 的大作中提到】 : 抱歉我看错题了。。 : 这题你把矩阵转45度,就可以转化成按层计算了呀 : 比如说 : 1 2 5 : 3 4 6 : 转化成 : 1 : 3 2 : 4 5 : 6
|
c********w 发帖数: 2438 | 6 你只能move right或者down
你用一维矩阵
move right的时候是不是相当于从f[j-1] move过来的a[i][j]=a[i][j-1]
move down的时候相当于就是本身f[j], i.e., a[i][j]=a[i-1][j]
每次update的时候转移函数就是
f[j]=grid[i][j]+Math.min(f[j], f[j-1])
需要的话我po我的代码,虽然很ugly…… |
s**********r 发帖数: 8153 | 7 快po,最好有讲解。
网上好多版本一维矩阵,都没讲解阿,看不懂怎么滚动的。
谢了!
【在 c********w 的大作中提到】 : 你只能move right或者down : 你用一维矩阵 : move right的时候是不是相当于从f[j-1] move过来的a[i][j]=a[i][j-1] : move down的时候相当于就是本身f[j], i.e., a[i][j]=a[i-1][j] : 每次update的时候转移函数就是 : f[j]=grid[i][j]+Math.min(f[j], f[j-1]) : 需要的话我po我的代码,虽然很ugly……
|
s**********r 发帖数: 8153 | 8 你算是说中要害了,我就是这个转移函数没看懂。。。
啥意思阿!
【在 c********w 的大作中提到】 : 你只能move right或者down : 你用一维矩阵 : move right的时候是不是相当于从f[j-1] move过来的a[i][j]=a[i][j-1] : move down的时候相当于就是本身f[j], i.e., a[i][j]=a[i-1][j] : 每次update的时候转移函数就是 : f[j]=grid[i][j]+Math.min(f[j], f[j-1]) : 需要的话我po我的代码,虽然很ugly……
|
c********w 发帖数: 2438 | 9 import java.util.*;
public class Solution{
public int minPathSum(int[][] grid){
int m=grid.length;
int n=grid[0].length;
int[] f=new int[n];
f[0]=grid[0][0];
for(int j=1;j
f[j]=grid[0][j]+f[j-1];
for(int i=1;i
f[0]+=grid[i][0];
for(int j=1;j
f[j]=grid[i][j]+Math.min(f[j], f[j-1]);
}
}
return f[n-1];
}
}
我的也木有comment,而且写的很不简洁…… |
s**********r 发帖数: 8153 | 10 我还是转不过弯,那个转移函数。。。
其实我就是有一个解法之后,容易禁锢在以前的思想里跳不出来。。。
【在 c********w 的大作中提到】 : import java.util.*; : public class Solution{ : public int minPathSum(int[][] grid){ : int m=grid.length; : int n=grid[0].length; : int[] f=new int[n]; : f[0]=grid[0][0]; : for(int j=1;j: f[j]=grid[0][j]+f[j-1]; : for(int i=1;i
|
|
|
c********w 发帖数: 2438 | 11 你拿笔写一个矩阵
先写个二维的
然后一维的再写一下试试 |
s**********r 发帖数: 8153 | 12 二维的我会,但一维的,我从根本就不明白要干啥。。。
【在 c********w 的大作中提到】 : 你拿笔写一个矩阵 : 先写个二维的 : 然后一维的再写一下试试
|
c********w 发帖数: 2438 | 13 等会啊
【在 s**********r 的大作中提到】 : 二维的我会,但一维的,我从根本就不明白要干啥。。。
|
s**********r 发帖数: 8153 | 14 haha 好
【在 c********w 的大作中提到】 : 等会啊
|
c********w 发帖数: 2438 | 15 就是
其实你每次更新的时候
只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1]
有关
然后你忽略i这个行变量的话,剩下的不就是a[j]和a[j-1]么 |
s**********r 发帖数: 8153 | 16 嘿嘿,我读你的代码,一行行代入,就明白了 :)
这东西,只能意会,还真难言传!
【在 c********w 的大作中提到】 : 就是 : 其实你每次更新的时候 : 只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1] : 有关 : 然后你忽略i这个行变量的话,剩下的不就是a[j]和a[j-1]么
|
c******a 发帖数: 789 | 17 我也看明白了。既然是一排排算下去的,算过用过的就可以丢弃了。所以用一维就够了
。真不错! |
s**********r 发帖数: 8153 | 18 哈哈,你很久以前没刷过这个么。。。哈哈
【在 c******a 的大作中提到】 : 我也看明白了。既然是一排排算下去的,算过用过的就可以丢弃了。所以用一维就够了 : 。真不错!
|
c******a 发帖数: 789 | 19 哈哈,我还特意翻出以前刷的code,2维的也过了大oj。
今天才听说能用一维来做,eye opening阿!
【在 s**********r 的大作中提到】 : 哈哈,你很久以前没刷过这个么。。。哈哈
|
s**********r 发帖数: 8153 | 20 2d的可以过大oj?
还好我先搜的别人的做法。
我自己只会2d的。如果我先写了,过了大oj,我肯定不求甚解了。
话说现在做法,大部分人,都用一维了。
【在 c******a 的大作中提到】 : 哈哈,我还特意翻出以前刷的code,2维的也过了大oj。 : 今天才听说能用一维来做,eye opening阿!
|