leetcode jump game 用一维DP做 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode jump game 用一维DP做

leetcode jump game 用一维DP做# JobHunting - 待字闺中

l*t2015-01-18 08:01

1 楼

之前用二维dp能过oj, 这次做貌似就超时了。。
查了一下可以用一维dp来搞（http://fisherlei.blogspot.com/2012/12/leetcode-jump-game.html）。。。看完答案觉得挺合理的，但是要是自己想的话怎么能直接想到用一维的来做呢？因为感觉写二维递推式是最直观的。。。DP这个思维总是建立不起来啊，求各位高人指点！

S*02015-01-18 08:01

2 楼

其实你把他这个dp理解为greedy，就好想了，说白了，就是你走到第i步时，如果剩余
的步数小于A[i]，就更新下步数，如果还没到最后一个index就走完了，就return
false。
这是我的code
bool canJump(int A[], int n) {
int left = 1;
for (int i = 0; i < n; i++) {
left--;
left = max(left, A[i]);
if (left == 0 && i < n-1) return false;
}
return true;
}

【在 l*******t 的大作中提到】

: 之前用二维dp能过oj, 这次做貌似就超时了。。
: 查了一下可以用一维dp来搞（http://fisherlei.blogspot.com/2012/12/leetcode-jump-game.html）。。。看完答案觉得挺合理的，但是要是自己想的话怎么能直接想到用一维的来做呢？因为感觉写二维递推式是最直观的。。。DP这个思维总是建立不起来啊，求各位高人指点！

l*t2015-01-18 08:01

3 楼

thx!

【在 S********0 的大作中提到】

:
: 其实你把他这个dp理解为greedy，就好想了，说白了，就是你走到第i步时，如果剩余
: 的步数小于A[i]，就更新下步数，如果还没到最后一个index就走完了，就return
: false。
: 这是我的code
: bool canJump(int A[], int n) {
: int left = 1;
: for (int i = 0; i < n; i++) {
: left--;
: left = max(left, A[i]);