c*8
2 楼
最近上瘾了，玩到D4就必须看攻略了。。
r*h
3 楼
因为当前行的值只和上一行有关，所以用
c[n%2]表示当前行，c[1-n%2]表示上一行即可
c[n%2]表示当前行，c[1-n%2]表示上一行即可
s*r
4 楼
这就更不明白了。当前的值应该和下一行和右边都有关阿。不是可以向右和下边走么？
【在 r**h 的大作中提到】
: 因为当前行的值只和上一行有关，所以用
: c[n%2]表示当前行，c[1-n%2]表示上一行即可
【在 r**h 的大作中提到】
: 因为当前行的值只和上一行有关，所以用
: c[n%2]表示当前行，c[1-n%2]表示上一行即可
r*h
5 楼
抱歉我看错题了。。
这题你把矩阵转45度，就可以转化成按层计算了呀
比如说
1 2 5
3 4 6
转化成
1
3 2
4 5
6
找一个从1到6得到path，然后就可以应用那个方法了
能分享一下用一维矩阵的代码吗？
这题你把矩阵转45度，就可以转化成按层计算了呀
比如说
1 2 5
3 4 6
转化成
1
3 2
4 5
6
找一个从1到6得到path，然后就可以应用那个方法了
能分享一下用一维矩阵的代码吗？
s*r
6 楼
阿？你这个方法我越说越糊涂了。
到处用的都是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
到处用的都是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
7 楼
你只能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……
你用一维矩阵
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
8 楼
快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……
网上好多版本一维矩阵，都没讲解阿，看不懂怎么滚动的。
谢了！
【在 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
9 楼
你算是说中要害了，我就是这个转移函数没看懂。。。
啥意思阿！
【在 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 的大作中提到】
: 你只能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
10 楼
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
for(int i=1;i
for(int j=1;j
}
}
return f[n-1];
}
}
我的也木有comment，而且写的很不简洁……
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
for(int i=1;i
for(int j=1;j
}
}
return f[n-1];
}
}
我的也木有comment，而且写的很不简洁……
s*r
11 楼
我还是转不过弯，那个转移函数。。。
其实我就是有一个解法之后，容易禁锢在以前的思想里跳不出来。。。
【在 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
: for(int i=1;i
其实我就是有一个解法之后，容易禁锢在以前的思想里跳不出来。。。
【在 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
: for(int i=1;i
c*w
12 楼
你拿笔写一个矩阵
先写个二维的
然后一维的再写一下试试
先写个二维的
然后一维的再写一下试试
s*r
13 楼
二维的我会，但一维的，我从根本就不明白要干啥。。。
【在 c********w 的大作中提到】
: 你拿笔写一个矩阵
: 先写个二维的
: 然后一维的再写一下试试
【在 c********w 的大作中提到】
: 你拿笔写一个矩阵
: 先写个二维的
: 然后一维的再写一下试试
c*w
14 楼
等会啊
【在 s**********r 的大作中提到】
: 二维的我会，但一维的，我从根本就不明白要干啥。。。
【在 s**********r 的大作中提到】
: 二维的我会，但一维的，我从根本就不明白要干啥。。。
s*r
15 楼
haha 好
【在 c********w 的大作中提到】
: 等会啊
【在 c********w 的大作中提到】
: 等会啊
c*w
16 楼
就是
其实你每次更新的时候
只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1]
有关
然后你忽略i这个行变量的话，剩下的不就是a[j]和a[j-1]么
其实你每次更新的时候
只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1]
有关
然后你忽略i这个行变量的话，剩下的不就是a[j]和a[j-1]么
s*r
17 楼
嘿嘿，我读你的代码，一行行代入，就明白了 :)
这东西，只能意会，还真难言传！
【在 c********w 的大作中提到】
: 就是
: 其实你每次更新的时候
: 只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1]
: 有关
: 然后你忽略i这个行变量的话，剩下的不就是a[j]和a[j-1]么
这东西，只能意会，还真难言传！
【在 c********w 的大作中提到】
: 就是
: 其实你每次更新的时候
: 只是跟需要更新的那个元素比如a[i][j]的正上方a[i-1][j]和同一行左方的a[i][j-1]
: 有关
: 然后你忽略i这个行变量的话，剩下的不就是a[j]和a[j-1]么
c*a
18 楼
我也看明白了。既然是一排排算下去的，算过用过的就可以丢弃了。所以用一维就够了
。真不错！
。真不错！
s*r
19 楼
哈哈，你很久以前没刷过这个么。。。哈哈
【在 c******a 的大作中提到】
: 我也看明白了。既然是一排排算下去的，算过用过的就可以丢弃了。所以用一维就够了
: 。真不错！
【在 c******a 的大作中提到】
: 我也看明白了。既然是一排排算下去的，算过用过的就可以丢弃了。所以用一维就够了
: 。真不错！
c*a
20 楼
哈哈，我还特意翻出以前刷的code，2维的也过了大oj。
今天才听说能用一维来做，eye opening阿！
【在 s**********r 的大作中提到】
: 哈哈，你很久以前没刷过这个么。。。哈哈
今天才听说能用一维来做，eye opening阿！
【在 s**********r 的大作中提到】
: 哈哈，你很久以前没刷过这个么。。。哈哈
s*r
21 楼
2d的可以过大oj？
还好我先搜的别人的做法。
我自己只会2d的。如果我先写了，过了大oj，我肯定不求甚解了。
话说现在做法，大部分人，都用一维了。
【在 c******a 的大作中提到】
: 哈哈，我还特意翻出以前刷的code，2维的也过了大oj。
: 今天才听说能用一维来做，eye opening阿！
还好我先搜的别人的做法。
我自己只会2d的。如果我先写了，过了大oj，我肯定不求甚解了。
话说现在做法，大部分人，都用一维了。
【在 c******a 的大作中提到】
: 哈哈，我还特意翻出以前刷的code，2维的也过了大oj。
: 今天才听说能用一维来做，eye opening阿！
相关阅读
Surface RT review 出来了sero-p在best buy买手机今天去T-MOBILE把玩了一下NOTE 2，明天就要上市了。果子带头提高价格, 有效阻止狗狗把市场带进价格战的漩涡T-mobile有wifi calling功能最便宜的手机是啥？mini乏善可陈，于是搞个ipad 4混淆视听T-Mobile发不出短信的问题真是让人干着急可以在电脑上发传真fax吗tmobile note 2 只要 $279 ~ $250国内真的不能用google voice 吗 (转载)晚上差点就买了tmobil的无合同note2damn ATT Note II need to wait 2 extra weeksSurface Pro带stylus吗？男人用什么手机，女人用什么手机， gay & les又分别用什么手机Surface有蓝牙吗？来，Atom的板子来了，649！有什么类似cityID的app么安卓有能同步读书进度的中文读书软件吗？早就说过了，等Win8平板出来，怕是平板的风也过了MetroTalk今天免费