j******2
发帖数: 362 | 1 每次跳到能跳的最远，结果就是最小步数吗？这个是个greedy吧，能讨论下怎么证明吗
？实在是个新手。
greedy algorithm:
starting at position i, jumping step j, the size of jump j is the one that
achieves max reach from step j-1 to step j.
Proof:
(1) step j is also the max reach from step 0 to step j.
(2) if there exists another strategy that results in fewer total steps, then
there must exist a step (step K1) that covers entirely a step (step K2) in
the greedy strategy. Namely, step K1's start <=step K2's start && step K1's
end>step K2's end. It contradicts the fact that step K2's end is the max
reach from all steps before it. |
j********x
发帖数: 2330 | 2 根据如下结论：
1. 如果n步只能到达的距离超过某点d，则到达d的最小步数一定小于或等于n
2. 如果n步能到达的最远距离达不到d，则到达d的最小部署一定大于n
3. n+1 步能到达的距离不会比n步小
问题变成求使得到达距离大于给定输入的最小步数；问题可以变成求n=[1,...,n]步能
走的最大范围是多少；这个是DP问题
dp[n] = max{i + A[i]} (i <= dp[n-1])
然后有个优化，i这里其实不需要每次从1开始搜索，因为i+A[i]本身只跟i有关系，只
需要一个循环检查所有i就可以，并且在过程中记录当前步数及其对应的距离，并且在
必要的时候更新。
int jump_gameII(int[] A) {
if (A.length <= 1) { return 0; }
int cur = 0
int step = 0;
int max = 0;
for (int i = 0; i < A.length && max < A.length - 1; ++i) {
if (i > cur && i <= max) {
++step;
cur = max;
} else if (i > max) {
return -1;// cannot move forward
}
max = max(max, i + A[i]);
}
if (cur < A.length - 1) {
return step + 1;
} else {
return step;
}
} |
n*******w
发帖数: 687 | 3 每次跳最远，结果不是最小步数。
反例
arr = [2, 2, 2, 100, 1, 1, 1]
2 2 1 1 1 需要4步
最后那个2跳1步到100是最快的。只需要3步。
greedy证明也有问题。
如果存在另一个strategy，并不能保证K1 cover K2。因为K1 K2可以是部分cover，交
叉的。比如反例里的情况。
then
in
s
【在 j******2 的大作中提到】
: 每次跳到能跳的最远，结果就是最小步数吗？这个是个greedy吧，能讨论下怎么证明吗
: ？实在是个新手。
: greedy algorithm:
: starting at position i, jumping step j, the size of jump j is the one that
: achieves max reach from step j-1 to step j.
: Proof:
: (1) step j is also the max reach from step 0 to step j.
: (2) if there exists another strategy that results in fewer total steps, then
: there must exist a step (step K1) that covers entirely a step (step K2) in
: the greedy strategy. Namely, step K1's start <=step K2's start && step K1's
|
n*******w
发帖数: 687 | 4 从前往后写递归式比较好写。
因为从后往前的话，跳到 i 的可能性太多，理论上可以从前面任意一个位置到i。
从前往后的话，i可以跳到 i+1, i+2, ..., i+A[i]
递归式是
P[i] = 1 + min { P[i+j] }
0
i从n-1往0解，返回P[0]
【在 j********x 的大作中提到】
: 根据如下结论：
: 1. 如果n步只能到达的距离超过某点d，则到达d的最小步数一定小于或等于n
: 2. 如果n步能到达的最远距离达不到d，则到达d的最小部署一定大于n
: 3. n+1 步能到达的距离不会比n步小
: 问题变成求使得到达距离大于给定输入的最小步数；问题可以变成求n=[1,...,n]步能
: 走的最大范围是多少；这个是DP问题
: dp[n] = max{i + A[i]} (i <= dp[n-1])
: 然后有个优化，i这里其实不需要每次从1开始搜索，因为i+A[i]本身只跟i有关系，只
: 需要一个循环检查所有i就可以，并且在过程中记录当前步数及其对应的距离，并且在
: 必要的时候更新。
|
y**k
发帖数: 222 | 5 LZ 可能是想说， 每步跳到某位置使得下一步能跳到最远的步数。 这个确实是对的。
由此可以构造线性算法。
假设现在在位置 i, 只需要检查 i+1,..., i+a[i] 这些位置上哪个 a[j] + j 值最大
， 那么就跳到那个位置。 下步要假定在位置 i+a[i], 能跳的步数要调整一下为 a[j]
+ j -(i+a[i]). |
n*******w
发帖数: 687 | 6 试试
2 4 2 100 1 1 1 1 1
这题应该是没法greedy的。每次choice之后有A[i]种可能性，每种可能性之后的
subproblem都可能包含最优解。所以无法保证greedy choice之后的subproblem包含最
优解继续greedy choice。
。
j]
【在 y**k 的大作中提到】
: LZ 可能是想说， 每步跳到某位置使得下一步能跳到最远的步数。 这个确实是对的。
: 由此可以构造线性算法。
: 假设现在在位置 i, 只需要检查 i+1,..., i+a[i] 这些位置上哪个 a[j] + j 值最大
: ， 那么就跳到那个位置。 下步要假定在位置 i+a[i], 能跳的步数要调整一下为 a[j]
: + j -(i+a[i]).
|
y**k
发帖数: 222 | 7 你可能没理解我的意思。不需要考虑那么多子问题的。用你的例子来说明吧。
第一步，在位置0，最大步长为2，考虑a[1]+1 和a[2]+2谁大，所以实际跳到位置1，但
是把问题化为在位置2，最大步长由a[1]=4 调整为a[1]+1-2=3。
第二步，在位置2，最大步长为3。••••
【在 n*******w 的大作中提到】
: 试试
: 2 4 2 100 1 1 1 1 1
: 这题应该是没法greedy的。每次choice之后有A[i]种可能性，每种可能性之后的
: subproblem都可能包含最优解。所以无法保证greedy choice之后的subproblem包含最
: 优解继续greedy choice。
:
: 。
: j]
|
y**k
发帖数: 222 | 8 这个不是回复， 只是借你的例子。
需要多少步跟下面问题有关：
序列 b[i]= max(a[j]+j), j<=i 有多少个台阶
2 5 5 103 103 103 103 103 103
之所以只说有关是因为还有其他一些简单条件要满足。
【在 n*******w 的大作中提到】
: 试试
: 2 4 2 100 1 1 1 1 1
: 这题应该是没法greedy的。每次choice之后有A[i]种可能性，每种可能性之后的
: subproblem都可能包含最优解。所以无法保证greedy choice之后的subproblem包含最
: 优解继续greedy choice。
:
: 。
: j]
|
n*******w
发帖数: 687 | 9 哦，实际是DP。理解了。。。lz的确实没看懂。。。
【在 y**k 的大作中提到】
: 你可能没理解我的意思。不需要考虑那么多子问题的。用你的例子来说明吧。
: 第一步，在位置0，最大步长为2，考虑a[1]+1 和a[2]+2谁大，所以实际跳到位置1，但
: 是把问题化为在位置2，最大步长由a[1]=4 调整为a[1]+1-2=3。
: 第二步，在位置2，最大步长为3。••••
|
c****7
发帖数: 4192 | 10 我这样是greedy吗？
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;j
if(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
从最后一个开始，看从最前面哪一个可以跳到最后，找到就break，算一步。再从前往
后找，找到第一个就break，算第2步，直到第一个。我这个greedy是从后往前，好像没
有逻辑错误呀。
then
in
s
【在 j******2 的大作中提到】
: 每次跳到能跳的最远，结果就是最小步数吗？这个是个greedy吧，能讨论下怎么证明吗
: ？实在是个新手。
: greedy algorithm:
: starting at position i, jumping step j, the size of jump j is the one that
: achieves max reach from step j-1 to step j.
: Proof:
: (1) step j is also the max reach from step 0 to step j.
: (2) if there exists another strategy that results in fewer total steps, then
: there must exist a step (step K1) that covers entirely a step (step K2) in
: the greedy strategy. Namely, step K1's start <=step K2's start && step K1's
|
c****7
发帖数: 4192 | 11 用我这个算法：
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;j
if(A[j]+j>=i){
step++;
i=j;
break;
}
}
}
return step;
}
i=6 step=0;
i=3 step=1;
i=1 step=2;
i=0 step=3;
每次greedy最小的能到当前节点的节点。空间1，时间最坏是O(n^2),最好是O(1)
【在 n*******w 的大作中提到】
: 每次跳最远，结果不是最小步数。
: 反例
: arr = [2, 2, 2, 100, 1, 1, 1]
: 2 2 1 1 1 需要4步
: 最后那个2跳1步到100是最快的。只需要3步。
: greedy证明也有问题。
: 如果存在另一个strategy，并不能保证K1 cover K2。因为K1 K2可以是部分cover，交
: 叉的。比如反例里的情况。
:
: then
|
j******2
发帖数: 362 | 12 我确实是这意思。但是现在我也觉得好像这个不是greedy了，但是为何是dp，却也还没
有想的很清楚。。。惭愧
或许只算有几步，而不是问每步怎么走，我这个greedy的解释也还行得通。
还要再想想。
。
j]
【在 y**k 的大作中提到】
: LZ 可能是想说， 每步跳到某位置使得下一步能跳到最远的步数。 这个确实是对的。
: 由此可以构造线性算法。
: 假设现在在位置 i, 只需要检查 i+1,..., i+a[i] 这些位置上哪个 a[j] + j 值最大
: ， 那么就跳到那个位置。 下步要假定在位置 i+a[i], 能跳的步数要调整一下为 a[j]
: + j -(i+a[i]).
|
