logo
Redian新闻
>未名空间
>pets - 心有所宠
>
跟风，阿pu，一起奔~
avatar
跟风，阿pu，一起奔~# pets - 心有所宠
j*2
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.
avatar
k*e
2 楼
管它什么节，跟风不孤单，lol~
avatar
j*x
3 楼
根据如下结论：
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;
}
}
avatar
s*s
4 楼
美女！！！！！！！！！！
我最喜欢这种秀气型的了！！！
avatar
n*w
5 楼
每次跳最远，结果不是最小步数。
反例
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
avatar
y*u
6 楼
美女！很和谐的一对！
avatar
n*w
7 楼
从前往后写递归式比较好写。
因为从后往前的话，跳到 i 的可能性太多，理论上可以从前面任意一个位置到i。
从前往后的话，i可以跳到 i+1, i+2, ..., i+A[i]
递归式是
P[i] = 1 + min { P[i+j] }
0i从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就可以，并且在过程中记录当前步数及其对应的距离，并且在
: 必要的时候更新。
avatar
s*s
8 楼
美女+大狗真心完美组合啊~~~
avatar
y*k
9 楼
LZ 可能是想说， 每步跳到某位置使得下一步能跳到最远的步数。 这个确实是对的。
由此可以构造线性算法。
假设现在在位置 i, 只需要检查 i+1,..., i+a[i] 这些位置上哪个 a[j] + j 值最大
， 那么就跳到那个位置。 下步要假定在位置 i+a[i], 能跳的步数要调整一下为 a[j]
+ j -(i+a[i]).
avatar
b*2
10 楼
nice

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
n*w
11 楼
试试
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]).
avatar
p*o
12 楼
赞美女~~~~~~~~~~~~
和狗狗在一起太和谐了
avatar
y*k
13 楼
你可能没理解我的意思。不需要考虑那么多子问题的。用你的例子来说明吧。
第一步，在位置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]
avatar
y*a
14 楼
赞美女大方奔及D3S神机
avatar
y*k
15 楼
这个不是回复， 只是借你的例子。
需要多少步跟下面问题有关：
序列 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]
avatar
K*t
16 楼
啊啊啊 今天这是什么日子啊 美女一片接一片啊~~~~头晕咧头晕咧。。。
avatar
n*w
17 楼
哦，实际是DP。理解了。。。lz的确实没看懂。。。

【在 y**k 的大作中提到】
: 你可能没理解我的意思。不需要考虑那么多子问题的。用你的例子来说明吧。
: 第一步，在位置0，最大步长为2，考虑a[1]+1 和a[2]+2谁大，所以实际跳到位置1，但
: 是把问题化为在位置2，最大步长由a[1]=4 调整为a[1]+1-2=3。
: 第二步，在位置2，最大步长为3。••••
avatar
A*u
18 楼
真美女啊
avatar
c*7
19 楼
我这样是greedy吗？
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;jif(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
avatar
k*e
20 楼
这让pu爹实在很嫉妒啊。。。

【在 y*********u 的大作中提到】
: 美女！很和谐的一对！
avatar
c*7
21 楼
用我这个算法：
public int jump(int[] A) {
int i=A.length-1;
int step=0;
while(i>0){
for(int j=0;jif(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
avatar
k*e
22 楼
我记得当初你说过如果我奔你就奔的哦，不能食言啊~

【在 K******t 的大作中提到】
: 啊啊啊 今天这是什么日子啊 美女一片接一片啊~~~~头晕咧头晕咧。。。
avatar
j*2
23 楼
我确实是这意思。但是现在我也觉得好像这个不是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]).
avatar
N*y
24 楼
哇塞～～美～～超有气质啊～～
avatar
K*t
25 楼
啊 我还说过这样的话哦。。。

【在 k*******e 的大作中提到】
: 我记得当初你说过如果我奔你就奔的哦，不能食言啊~
avatar
k*e
26 楼
为了不占楼，俺在这里一起回。。 谢谢捧场~~~~ 很大声滴，很真心滴~~ (:

【在 p********o 的大作中提到】
: 赞美女~~~~~~~~~~~~
: 和狗狗在一起太和谐了
avatar
g*x
27 楼
wow，赞清秀美女！
avatar
I*s
28 楼
坐等片片！！！

【在 K******t 的大作中提到】
: 啊 我还说过这样的话哦。。。
avatar
k*e
29 楼
有滴，请查找 兮若妞儿的故事之十一——宝贝 生日快乐 贴，lol

【在 K******t 的大作中提到】
: 啊 我还说过这样的话哦。。。
avatar
l*o
30 楼
美女啊～～～
avatar
I*s
31 楼
真是赏心悦目啊。看的我立马都不困了。
avatar
m*u
32 楼
赚到了，今天看了好多美女。还有美猫美狗。
avatar
K*t
33 楼
真是人在江湖飘呀。。。哪有不挨刀呀lol

【在 k*******e 的大作中提到】
: 有滴，请查找 兮若妞儿的故事之十一——宝贝 生日快乐 贴，lol
avatar
b*t
34 楼
老爷不要死阿！

【在 K******t 的大作中提到】
: 真是人在江湖飘呀。。。哪有不挨刀呀lol
avatar
s*s
35 楼
所以，你就索性爽快的从了算了~~~

【在 K******t 的大作中提到】
: 真是人在江湖飘呀。。。哪有不挨刀呀lol
avatar
w*o
36 楼
喜欢清清爽爽的美女，赞！
avatar
w*r
37 楼
wow～PU妈好小哦看上去
avatar
a*e
38 楼
美女, where is afu daddy!

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
b*b
39 楼
美女+帅哥！！！
avatar
H*g
40 楼
拉风拉风啊～～～～～～～
avatar
d*1
41 楼
美女啊。旁边的帅哥已经赞过了。

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
a*b
42 楼
知性美女啊
avatar
a*s
43 楼
又一个美女
avatar
K*a
44 楼
好喜欢你家大狗！美女气质真好！
avatar
m*g
45 楼
你们俩看得我眼花缭乱，都不知道盯着谁好了。。。

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
o*n
46 楼
好有气质的美女呀~~~
avatar
K*t
47 楼
老爷没死。。。刚刚快饿死了。。。还好猫爹及时来搭救我lol

【在 b*******t 的大作中提到】
: 老爷不要死阿！
avatar
R*s
48 楼
re!

【在 N*****y 的大作中提到】
: 哇塞～～美～～超有气质啊～～
avatar
m*f
49 楼
a, 除了apu 家的美女其他的都没看到啊， 大家重新奔一次给我看吧。。。
avatar
P*2
50 楼
美女！！！！！！！！！！！！！！气质好极了！！！！！！

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
k*e
51 楼
谢谢以上的大家的捧场~~~
特别是Rosmarinus，俺跟风奔还有包子收，开心中~
avatar
e*t
52 楼
太美了。
avatar
b*s
53 楼
美女美狗！
avatar
Y*a
54 楼
Pu妈真是惊为天人呀。
嘿嘿
avatar
M*a
55 楼
还是那句，有什么样的美妈就有什么样美娃 :)
avatar
m*g
56 楼
能不能收？
avatar
b*r
57 楼
哇，好美
avatar
k*e
58 楼
这标准有点低啊，嘿。。。

【在 Y****a 的大作中提到】
: Pu妈真是惊为天人呀。
: 嘿嘿
avatar
k*e
59 楼
收啥？这是回错帖子了么？。。。=。=

【在 m*****g 的大作中提到】
: 能不能收？
avatar
m*u
60 楼
萌死了。。。。

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
s*d
61 楼
晕了

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
Y*a
62 楼

BSO！，嘿嘿。

【在 k*******e 的大作中提到】
: 这标准有点低啊，嘿。。。
avatar
y*o
63 楼
一个美一个萌呀
avatar
c*u
64 楼
美女和大狗我都喜欢死啦！！

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
a*e
65 楼
还是我们派慈的美女高质量！
娃也威风！
avatar
y*n
66 楼
路过的大赞一声太美了!
avatar
i*l
67 楼
美女太仙了！！
avatar
g*7
68 楼
气质美女啊，我高中时候就想变成这样的
avatar
p*t
69 楼
美女啊。存了。

【在 k*******e 的大作中提到】
: 管它什么节，跟风不孤单，lol~
avatar
z*e
70 楼
赞帅狗美女！
相关阅读
再次提醒，不要给宠物乱用人类的药物～狗狗怎么知道什么东西是自己的阿？猫节 狮子奔糊糊说，总奔shelter的猫，他嫉妒了。foscam deal!鬼节快乐，附鬼照，胆小者慎入还望在凤凰城，肯萨斯，米苏里，等区的同胞们能够站起来！这只金毛好可怜[参加活动]~~见习天使的故事~~（加大图了）飞吧大黑妞Houston 流浪小猫求收养小伙伴们开心迎节日 我家夺夺见天见医生某驴最近成了饿死鬼猫往家带别的猫参加活动 选美大赛志玲近况小熊今天去码头啦咪 抱腿是啥心理求助：狗狗皮肤病 （图）高手在民间，我家有个造型喵
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。