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阿！
|
