f家店面题 - 未名空间MITBBS历史存档

p*d2014-01-31 08:01

1 楼

跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
头上。问最少几步可以跳完整条河流。
给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
第一步先提速到2，再跳到R[2]；
第二步先提速到3，再跳到R[5]；
第三步保持速度3，跳出数组范围，成功过河。

l*62014-01-31 08:01

2 楼

int path[N];
size_t getStep(speed , pos)
if pos >= N return 0;
if path[pos] == 0 return INT_MAX ;
else return 1 + min (getStep(speed , pos + speed) , getStep(speed + 1 , pos
+ speed + 1));

compute getStep(1 , 0)
cache pair(speed , pos) to do dp

g*e2014-01-31 08:01

3 楼

good
INT_MAX+1 不安全吧

pos

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

: int path[N];
: size_t getStep(speed , pos)
: if pos >= N return 0;
: if path[pos] == 0 return INT_MAX ;
: else return 1 + min (getStep(speed , pos + speed) , getStep(speed + 1 , pos
: + speed + 1));
:
: compute getStep(1 , 0)
: cache pair(speed , pos) to do dp

l*62014-01-31 08:01

4 楼

Haha true, thanks for pointing it out

【在 g*********e 的大作中提到】

: good
: INT_MAX+1 不安全吧
:
: pos

d*u2014-01-31 08:01

5 楼

这题目好多人考

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

g*g2014-01-31 08:01

6 楼

DP解法：
i => 所在R数组位置
j => speed.
f(i,j)= min(f(i-j, j), f(i-j+1, j-1))
复杂度， O(n2)

p*22014-01-31 08:01

7 楼

R = [1,1,1,0,1,1,0,0]
n = R.length
dp = ([] for i in [0...n])

for i in [n-1..0]
for j in [1..n]
dp[i][j] = 1
dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

b*f2014-01-31 08:01

8 楼

mark

n*12014-01-31 08:01

9 楼

n的值感觉还能缩小

h*p2014-01-31 08:01

10 楼

求二爷解释下

【在 p*****2 的大作中提到】

: R = [1,1,1,0,1,1,0,0]
: n = R.length
: dp = ([] for i in [0...n])
:
: for i in [n-1..0]
: for j in [1..n]
: dp[i][j] = 1
: dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

p*d2014-01-31 08:01

11 楼

跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
头上。问最少几步可以跳完整条河流。
给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
第一步先提速到2，再跳到R[2]；
第二步先提速到3，再跳到R[5]；
第三步保持速度3，跳出数组范围，成功过河。

l*62014-01-31 08:01

12 楼

int path[N];
size_t getStep(speed , pos)
if pos >= N return 0;
if path[pos] == 0 return INT_MAX ;
else return 1 + min (getStep(speed , pos + speed) , getStep(speed + 1 , pos
+ speed + 1));

compute getStep(1 , 0)
cache pair(speed , pos) to do dp

g*e2014-01-31 08:01

13 楼

good
INT_MAX+1 不安全吧

pos

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

: int path[N];
: size_t getStep(speed , pos)
: if pos >= N return 0;
: if path[pos] == 0 return INT_MAX ;
: else return 1 + min (getStep(speed , pos + speed) , getStep(speed + 1 , pos
: + speed + 1));
:
: compute getStep(1 , 0)
: cache pair(speed , pos) to do dp

l*62014-01-31 08:01

14 楼

Haha true, thanks for pointing it out

【在 g*********e 的大作中提到】

: good
: INT_MAX+1 不安全吧
:
: pos

d*u2014-01-31 08:01

15 楼

这题目好多人考

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

g*g2014-01-31 08:01

16 楼

DP解法：
i => 所在R数组位置
j => speed.
f(i,j)= min(f(i-j, j), f(i-j+1, j-1))
复杂度， O(n2)

p*22014-01-31 08:01

17 楼

R = [1,1,1,0,1,1,0,0]
n = R.length
dp = ([] for i in [0...n])

for i in [n-1..0]
for j in [1..n]
dp[i][j] = 1
dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

b*f2014-01-31 08:01

18 楼

mark

n*12014-01-31 08:01

19 楼

n的值感觉还能缩小

h*p2014-01-31 08:01

20 楼

求二爷解释下

【在 p*****2 的大作中提到】

: R = [1,1,1,0,1,1,0,0]
: n = R.length
: dp = ([] for i in [0...n])
:
: for i in [n-1..0]
: for j in [1..n]
: dp[i][j] = 1
: dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

b*i2014-01-31 08:01

21 楼

用dp写这道题返回值该是多少呢？
然后遇到R[0]==0的情况该怎么处理呢？
写了半天dp也写不对。。。唉。。。

【在 p*****2 的大作中提到】

: R = [1,1,1,0,1,1,0,0]
: n = R.length
: dp = ([] for i in [0...n])
:
: for i in [n-1..0]
: for j in [1..n]
: dp[i][j] = 1
: dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

b*c2014-01-31 08:01

22 楼

這道題要小心，我面過，我當時算法複雜度是大概o(n sqrt(n))
因為 dp(i,j) 要滿足 2*j<= sqrt(9+8i)-1

l*a2014-01-31 08:01

23 楼

为什么非用DP?效率高吗
构造一个二叉树咋样？至少O(n)能找到结果吧

【在 g*****g 的大作中提到】

: DP解法：
: i => 所在R数组位置
: j => speed.
: f(i,j)= min(f(i-j, j), f(i-j+1, j-1))
: 复杂度， O(n2)

b*c2014-01-31 08:01

24 楼

樓上大牛，別調戲了，說說怎麼做啊

l*a2014-01-31 08:01

25 楼

你说哪位？
title都换了？

【在 b*****c 的大作中提到】

: 樓上大牛，別調戲了，說說怎麼做啊

s*p2014-01-31 08:01

26 楼

是不是应该有 O(n)的算法?
类似leetcode的jump game.

d*k2014-01-31 08:01

27 楼

这个貌似用贪心法就可以
和lc里面一道题很像

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

d*k2014-01-31 08:01

28 楼

对, 和Jump game 2很像

【在 s****p 的大作中提到】

: 是不是应该有 O(n)的算法?
: 类似leetcode的jump game.

v*y2014-01-31 08:01

29 楼

for speed in [max_speed ... 1]
for index in [length-1 ... 0]
if R==0
ways[speed][index] = Integer.MAX
else
if speed+index>length-1
ways[speed][inde] = 1
else
ways[speed][index] += min(ways[speed][index+speed], ways[speed+
1][index+speed])
return min(ways[1][0], ways[2][0]);

i*u2014-01-31 08:01

30 楼

贪心不保证得到解
R=[1,1,1,0,1,1,1,1，0，0]

【在 d**k 的大作中提到】

: 这个貌似用贪心法就可以
: 和lc里面一道题很像

o*g2014-01-31 08:01

31 楼

贪心不成是要回退的

【在 i***u 的大作中提到】

: 贪心不保证得到解
: R=[1,1,1,0,1,1,1,1，0，0]

i*u2014-01-31 08:01

32 楼

请搞清楚贪心和dp区别再来发言
We can make whatever choice seems best at the moment and then solve the
subproblems that arise later. The choice made by a greedy algorithm may
depend on choices made so far but not on future choices or all the solutions
to the subproblem. It iteratively makes one greedy choice after another,
reducing each given problem into a smaller one. In other words, a greedy
algorithm never reconsiders its choices. This is the main difference from
dynamic programming, which is exhaustive and is guaranteed to find the
solution.

【在 o***g 的大作中提到】

: 贪心不成是要回退的

y*n2014-01-31 08:01

33 楼

mark

v*l2014-01-31 08:01

34 楼

DFS 应该可以

b*i2014-01-31 08:01

35 楼

用dp写这道题返回值该是多少呢？
然后遇到R[0]==0的情况该怎么处理呢？
写了半天dp也写不对。。。唉。。。

【在 p*****2 的大作中提到】

: R = [1,1,1,0,1,1,0,0]
: n = R.length
: dp = ([] for i in [0...n])
:
: for i in [n-1..0]
: for j in [1..n]
: dp[i][j] = 1
: dp[i][j] += Math.min(dp[i+j][j], dp[i+j+1][j+1]) if i+j+1 < n

b*c2014-01-31 08:01

36 楼

這道題要小心，我面過，我當時算法複雜度是大概o(n sqrt(n))
因為 dp(i,j) 要滿足 2*j<= sqrt(9+8i)-1

l*a2014-01-31 08:01

37 楼

为什么非用DP?效率高吗
构造一个二叉树咋样？至少O(n)能找到结果吧

【在 g*****g 的大作中提到】

: DP解法：
: i => 所在R数组位置
: j => speed.
: f(i,j)= min(f(i-j, j), f(i-j+1, j-1))
: 复杂度， O(n2)

b*c2014-01-31 08:01

38 楼

樓上大牛，別調戲了，說說怎麼做啊

l*a2014-01-31 08:01

39 楼

你说哪位？
title都换了？

【在 b*****c 的大作中提到】

: 樓上大牛，別調戲了，說說怎麼做啊

s*p2014-01-31 08:01

40 楼

是不是应该有 O(n)的算法?
类似leetcode的jump game.

d*k2014-01-31 08:01

41 楼

这个貌似用贪心法就可以
和lc里面一道题很像

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

d*k2014-01-31 08:01

42 楼

对, 和Jump game 2很像

【在 s****p 的大作中提到】

: 是不是应该有 O(n)的算法?
: 类似leetcode的jump game.

v*y2014-01-31 08:01

43 楼

for speed in [max_speed ... 1]
for index in [length-1 ... 0]
if R==0
ways[speed][index] = Integer.MAX
else
if speed+index>length-1
ways[speed][inde] = 1
else
ways[speed][index] += min(ways[speed][index+speed], ways[speed+
1][index+speed])
return min(ways[1][0], ways[2][0]);

i*u2014-01-31 08:01

44 楼

贪心不保证得到解
R=[1,1,1,0,1,1,1,1，0，0]

【在 d**k 的大作中提到】

: 这个貌似用贪心法就可以
: 和lc里面一道题很像

o*g2014-01-31 08:01

45 楼

贪心不成是要回退的

【在 i***u 的大作中提到】

: 贪心不保证得到解
: R=[1,1,1,0,1,1,1,1，0，0]

i*u2014-01-31 08:01

46 楼

请搞清楚贪心和dp区别再来发言
We can make whatever choice seems best at the moment and then solve the
subproblems that arise later. The choice made by a greedy algorithm may
depend on choices made so far but not on future choices or all the solutions
to the subproblem. It iteratively makes one greedy choice after another,
reducing each given problem into a smaller one. In other words, a greedy
algorithm never reconsiders its choices. This is the main difference from
dynamic programming, which is exhaustive and is guaranteed to find the
solution.

【在 o***g 的大作中提到】

: 贪心不成是要回退的

y*n2014-01-31 08:01

47 楼

mark

v*l2014-01-31 08:01

48 楼

DFS 应该可以

f*t2014-01-31 08:01

49 楼

int FlogCrossRiver(string river) {
if (river.empty()) {
return 0;
}
vector>> vp(river.size());
vp[0].emplace_back(1, 1);
int res = INT_MAX;
for (size_t i = 0; i < vp.size(); ++i) {
if (river[i] == '0') {
continue;
}
for (auto pr : vp[i]) {
if (i + pr.first >= vp.size()) {
res = min(pr.second, res);
} else if (river[i + pr.first] == '1') {
vp[i + pr.first].emplace_back(pr.first, pr.second + 1);
}
if (i + pr.first + 1 >= vp.size()) {
res = min(pr.second, res);
} else if (river[i + pr.first + 1] == '1') {
vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1);
}
}
}
return res;
}
void FlogCrossRiverTest() {
cout << "11101100t" << FlogCrossRiver("11101100") << endl;
cout << "11111111t" << FlogCrossRiver("11111111") << endl;
cout << "11101000t" << FlogCrossRiver("11101000") << endl;
cout << "11010101t" << FlogCrossRiver("11010101") << endl;
}

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

l*02014-01-31 08:01

50 楼

A recursive solution
public int solve(int[] R) {
return solve(R, 0, 1, 0);
}
public int solve(int[] R, int offset, int speed, int stepsTaken) {
if(offset + speed + 1 >= R.length) return stepsTaken + 1;
int minSteps = Integer.MAX_VALUE;
if(R[offset + speed] == 1)
minSteps = Math.min(minSteps, solve(R, offset + speed, speed,
stepsTaken + 1));
if(R[offset + speed + 1] == 1)
minSteps = Math.min(minSteps, solve(R, offset + speed + 1,
speed + 1, stepsTaken + 1));
return minSteps;
}

l*s2014-01-31 08:01

51 楼

dp[i][j]: 以速度 j 走到第 i 个位置的最少步数
dp[i][j] = min(dp[i-j][j], dp[i-j][j-1])+1
ans = min(dp[i][j], where i+j+1>=n) + 1

t*y2014-01-31 08:01

52 楼

this is the best answer for this question in this post

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

: int FlogCrossRiver(string river) {
: if (river.empty()) {
: return 0;
: }
: vector>> vp(river.size());
: vp[0].emplace_back(1, 1);
: int res = INT_MAX;
: for (size_t i = 0; i < vp.size(); ++i) {
: if (river[i] == '0') {
: continue;

j*32014-01-31 08:01

53 楼

mark

a*y2014-01-31 08:01

54 楼

贪心可以么?
int JumpMin(const std::vector& input) {
int pos = 0;
int speed = 2;
int num = 0;
while (pos + speed < input.size()) {
++num;
pos += speed;
++speed;
while (speed > 0 && input[pos] == 0) {
--pos;
--speed;
}
if (speed <= 0) {
return -1;
}
}
return num;
}

M*w2014-01-31 08:01

55 楼

Complexity analysis for this problem
Maximum speed m will get if array items are 1s
1+2+...m < n+m // Can jump m-1 step out of array
m(m-1)/2m < sqrt(2n)
Max distance traved should be n+m-1
Therefore DP matrix [Pos speed] size should be (n+m-1)*m = O(n*sqrt(n))

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

f*t2014-01-31 08:01

56 楼

int FlogCrossRiver(string river) {
if (river.empty()) {
return 0;
}
vector>> vp(river.size());
vp[0].emplace_back(1, 1);
int res = INT_MAX;
for (size_t i = 0; i < vp.size(); ++i) {
if (river[i] == '0') {
continue;
}
for (auto pr : vp[i]) {
if (i + pr.first >= vp.size()) {
res = min(pr.second, res);
} else if (river[i + pr.first] == '1') {
vp[i + pr.first].emplace_back(pr.first, pr.second + 1);
}
if (i + pr.first + 1 >= vp.size()) {
res = min(pr.second, res);
} else if (river[i + pr.first + 1] == '1') {
vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1);
}
}
}
return res;
}
void FlogCrossRiverTest() {
cout << "11101100t" << FlogCrossRiver("11101100") << endl;
cout << "11111111t" << FlogCrossRiver("11111111") << endl;
cout << "11101000t" << FlogCrossRiver("11101000") << endl;
cout << "11010101t" << FlogCrossRiver("11010101") << endl;
}

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

l*02014-01-31 08:01

57 楼

A recursive solution
public int solve(int[] R) {
return solve(R, 0, 1, 0);
}
public int solve(int[] R, int offset, int speed, int stepsTaken) {
if(offset + speed + 1 >= R.length) return stepsTaken + 1;
int minSteps = Integer.MAX_VALUE;
if(R[offset + speed] == 1)
minSteps = Math.min(minSteps, solve(R, offset + speed, speed,
stepsTaken + 1));
if(R[offset + speed + 1] == 1)
minSteps = Math.min(minSteps, solve(R, offset + speed + 1,
speed + 1, stepsTaken + 1));
return minSteps;
}

l*s2014-01-31 08:01

58 楼

dp[i][j]: 以速度 j 走到第 i 个位置的最少步数
dp[i][j] = min(dp[i-j][j], dp[i-j][j-1])+1
ans = min(dp[i][j], where i+j+1>=n) + 1

t*y2014-01-31 08:01

59 楼

this is the best answer for this question in this post

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

: int FlogCrossRiver(string river) {
: if (river.empty()) {
: return 0;
: }
: vector>> vp(river.size());
: vp[0].emplace_back(1, 1);
: int res = INT_MAX;
: for (size_t i = 0; i < vp.size(); ++i) {
: if (river[i] == '0') {
: continue;

j*32014-01-31 08:01

60 楼

mark

a*y2014-01-31 08:01

61 楼

贪心可以么?
int JumpMin(const std::vector& input) {
int pos = 0;
int speed = 2;
int num = 0;
while (pos + speed < input.size()) {
++num;
pos += speed;
++speed;
while (speed > 0 && input[pos] == 0) {
--pos;
--speed;
}
if (speed <= 0) {
return -1;
}
}
return num;
}

M*w2014-01-31 08:01

62 楼

Complexity analysis for this problem
Maximum speed m will get if array items are 1s
1+2+...m < n+m // Can jump m-1 step out of array
m(m-1)/2m < sqrt(2n)
Max distance traved should be n+m-1
Therefore DP matrix [Pos speed] size should be (n+m-1)*m = O(n*sqrt(n))

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

a*02014-01-31 08:01

63 楼

是不是写错了？
dp[i][j] = min(dp[i-j][j], dp[i-j+1][j-1])+1 才对吧？

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

: dp[i][j]: 以速度 j 走到第 i 个位置的最少步数
: dp[i][j] = min(dp[i-j][j], dp[i-j][j-1])+1
: ans = min(dp[i][j], where i+j+1>=n) + 1

b*b2014-01-31 08:01

64 楼

greedy algo won't work in this case. If we change the problem a little bit,
e.g. at each stone, you can either increase current speed by 1, or reduce
speed to ANY thing between 1 to current speed, then greedy algo can work out
the solution in O(n).

【在 a*****y 的大作中提到】

: 贪心可以么?
: int JumpMin(const std::vector& input) {
: int pos = 0;
: int speed = 2;
: int num = 0;
: while (pos + speed < input.size()) {
: ++num;
: pos += speed;
: ++speed;
: while (speed > 0 && input[pos] == 0) {

l*s2014-01-31 08:01

65 楼

private int minHops(byte[] nums){
//dp[i,j] is hop times at pace amount j of each stone i
int[,] dp = new int[nums.Length, nums.Length];
if (nums.Length < 1 || nums[0] == 0) return -1;
for (int i = 0; i < nums.Length; i++){
if (nums[i] == 0) continue;
int maxHop = 2, minTimes = 1;
for (int j = 1; i - j >= 0; j++)
if (i < 3 && i - j == 0 || dp[i - j, j - 1] > 0){
dp[i, j - 1] = dp[i, j] = dp[i - j, j - 1] + 1;
maxHop = i + j + 1;
minTimes = dp[i, j] + 1;
}
if (maxHop > nums.Length - 1) return minTimes;
}
return -1;
}

T*U2014-01-31 08:01

66 楼

没有错，测了几个TEST CASE都没问题（假设有解）
public int getMinStep(int[] path){
int len = path.length;
// dp[i][j] is the min step to reach position i at speed j;
long[][] dp = new long[len + 1][len + 1];
Arrays.fill(dp[0], Integer.MAX_VALUE);
dp[0][1] = 0;
int ret = Integer.MAX_VALUE;
for(int i = 1; i < len; i++){
int maxSpeed = (int) Math.sqrt(9 + 8 * i) + 1;
Arrays.fill(dp[i], Integer.MAX_VALUE);
for(int j = 1; j <= Math.min(maxSpeed, i); j++){
if(path[i] == 0){
dp[i][j] = Integer.MAX_VALUE;
continue;
}
dp[i][j] = Math.min(dp[i - j][j], dp[i - j][j - 1]) + 1;
if(i + j + 1 >= len){
ret = (int) Math.min(ret, dp[i][j] + 1);
}
}
}
return ret;
}

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

:
: 是不是写错了？
: dp[i][j] = min(dp[i-j][j], dp[i-j+1][j-1])+1 才对吧？

r*n2014-01-31 08:01

67 楼

A method combine DP and greedy
object RiverJump {
def main(args: Array[String]) {
//val a = Array(1,1,1,0,1,1,0,0)
val a = Array(1,1,1,0,1,1,1,1, 0, 0)
val m = jump(a, 0, 1)
println(s"""$m""")
}
val set = new mutable.HashSet[(Int, Int)]()
def jump(r: Array[Int], start: Int, speed: Int): (Int, Boolean) = {
var ret: (Int, Boolean) = (Int.MaxValue, false)
if (start >= r.length) {
ret = (0, true)
} else if (set.contains(start, speed) || r(start) == 0) {
ret = (Int.MaxValue, false)
} else {
val s2 = jump(r, start + speed + 1, speed + 1)
if (s2._2) {
ret = (s2._1 + 1, s2._2)
} else {
val s1 = jump(r, start + speed, speed)
if (s1._2) {
ret = (s1._1 + 1, s1._2)
}
}
}
if (!ret._2) {
set.add((start, speed))
}
ret
}
}

b*n2014-01-31 08:01

68 楼

// Recursion approach
public class Solution {
public static void main(String[] args) {
Jump jump = new Jump();
int[] river1 = {1, 1, 1, 0, 1, 1, 0, 0};
System.out.println(jump.getMinSteps(river1));
int[] river2 = {1, 1, 1, 0, 1, 1, 1, 1, 0, 0};
System.out.println(jump.getMinSteps(river2));
}
}
class Jump {
private int min;
private int[] river;
public int getMinSteps(int[] river) {
this.river = river;
this.min = river.length;
recursiveJump(0, 0, 1);
return min;
}
public void recursiveJump(int start, int steps, int speed) {
if (start >= river.length) {
min = Math.min(min, steps);
return;
}
if (river[start] == 0) return;
recursiveJump(start + speed, steps + 1, speed);
recursiveJump(start + speed + 1, steps + 1, speed + 1);
}
}

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

i*y2014-01-31 08:01

69 楼

为什么是 (9+8*i) + 1?
int maxSpeed = (int) Math.sqrt(9 + 8 * i) + 1;

【在 T****U 的大作中提到】

: 没有错，测了几个TEST CASE都没问题（假设有解）
: public int getMinStep(int[] path){
: int len = path.length;
: // dp[i][j] is the min step to reach position i at speed j;
: long[][] dp = new long[len + 1][len + 1];
: Arrays.fill(dp[0], Integer.MAX_VALUE);
: dp[0][1] = 0;
: int ret = Integer.MAX_VALUE;
: for(int i = 1; i < len; i++){
: int maxSpeed = (int) Math.sqrt(9 + 8 * i) + 1;

b*a2014-01-31 08:01

70 楼

好像是 Jump Game II 稍加改动，楼主的case可以过
int jump(int* nums, int numsSize)
{
if (!nums || !numsSize) return -1;
else
{
int last = 0;
int cur = 0;
int jumps = 0;
int speed = 1;
int i;

for (i = 0; i < numsSize; i++)
{
if (i > last)
{
last = cur;
jumps++;
speed++;
}

if (nums[i] && (nums[i + speed] || (i + speed > numsSize - 1)) &
& ((i + speed) > cur))
cur = i + speed;

if (nums[i] && (nums[i + (speed + 1)] || (i + speed + 1 >
numsSize - 1)) && (i + (speed + 1) > cur))
cur = i + (speed + 1);
}
return jumps;
}
}
int main()
{
int in[8] = {1,1,1,0,1,1,0,0};
printf("%dn", jump(in, 8));

return 0;
}

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。

h*p2014-01-31 08:01

71 楼

大牛说下你的思路
传统DP不是N2吗，如何有效的我剪枝？2*j<= sqrt(9+8i)-1看不明白

【在 b*****c 的大作中提到】

: 這道題要小心，我面過，我當時算法複雜度是大概o(n sqrt(n))
: 因為 dp(i,j) 要滿足 2*j<= sqrt(9+8i)-1

f*s2014-01-31 08:01

72 楼

电面面这么难？

【在 p******d 的大作中提到】

: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，
: 初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石
: 头上。问最少几步可以跳完整条河流。
: 给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：
: 第一步先提速到2，再跳到R[2]；
: 第二步先提速到3，再跳到R[5]；
: 第三步保持速度3，跳出数组范围，成功过河。