p*****2
发帖数: 21240 | 1 感觉比DP难一个档次
DP还是比较容易的，毕竟属于brute force，miss不了啥东西。greedy就不一样了，很
难证明正确性，自己做了也不清楚到底对不对。想证明一下，发现特别费脑子。DP想起
来要清晰很多。看来做greedy的题还需要加强呀。 |
h**6
发帖数: 4160 | 2 贪婪算法的问题，看了答案后的反应是：啊？就这么简单，对不对啊？ |
p*****2
发帖数: 21240 | 3
大牛说的太形象了。能不能给点建议？
【在 h**6 的大作中提到】
: 贪婪算法的问题，看了答案后的反应是：啊？就这么简单，对不对啊？
|
s*****r
发帖数: 108 | 4 是的...刚开始学感觉 greedy 简单，dp 难搞
因为一开始做的 greedy 确实是简单题，dp 入门难一点
后来做多 dp 发现 dp 又容易写 准确率又高
而 greedy 就难搞了 牵扯到数学证明
其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
必深入 |
p*****2
发帖数: 21240 | 5
一看就是大牛。先膜拜一下。青蛙跳这个是哪里的竞赛题，貌似F的一道面试题。M<=
100是怎么回事？长度不是10^9这么长吗？能不能详细说说。
【在 s*****r 的大作中提到】
: 是的...刚开始学感觉 greedy 简单，dp 难搞
: 因为一开始做的 greedy 确实是简单题，dp 入门难一点
: 后来做多 dp 发现 dp 又容易写 准确率又高
: 而 greedy 就难搞了 牵扯到数学证明
: 其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
: 比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
: 100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
: 再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
: 还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
: 必深入
|
s*****r
发帖数: 108 | 6 啊 我错了...
这个是 noip 2005 过河
桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
过尾踩的最少 |
p*****2
发帖数: 21240 | 7
多谢。看来有竞赛经验的人面F有很大的优势。
【在 s*****r 的大作中提到】
: 啊 我错了...
: 这个是 noip 2005 过河
: 桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
: 过尾踩的最少
|
w****a
发帖数: 710 | 8 可以用DP但是greedy更简单，jump game就是个好例子啊。哈哈 |
p*****2
发帖数: 21240 | 9
jump game是greedy的吗？
【在 w****a 的大作中提到】
: 可以用DP但是greedy更简单，jump game就是个好例子啊。哈哈
|
c********t
发帖数: 5706 | 10 请问哪里有test cases？多谢！
【在 s*****r 的大作中提到】
: 啊 我错了...
: 这个是 noip 2005 过河
: 桥每个位置都可以踩 而青蛙不想踩到石子 石子有 1 <= M <= 100 个 青蛙希望从头跳
: 过尾踩的最少
|
c********t
发帖数: 5706 | 11 写了一个，大侠看看对不对，有没有什么可以优化的。
public int frogJump(int bridgeLength, int s, int t, int m,
HashSet stones) {
int[] dp = new int[bridgeLength + 1];
for (int i = s; i <= t; i++) {
if (stones.contains(i))
dp[i] = 1;
}
for (int i = t + 1; i <= bridgeLength; i++) {
int prev_stones = Integer.MAX_VALUE;
for (int j = s; j <= t; j++) {
prev_stones = Math.min(prev_stones, dp[i - j]);
}
dp[i] = prev_stones;
if (stones.contains(i))
dp[i]++;
}
return dp[bridgeLength];
}
【在 s*****r 的大作中提到】
: 是的...刚开始学感觉 greedy 简单，dp 难搞
: 因为一开始做的 greedy 确实是简单题，dp 入门难一点
: 后来做多 dp 发现 dp 又容易写 准确率又高
: 而 greedy 就难搞了 牵扯到数学证明
: 其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
: 比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
: 100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
: 再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
: 还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
: 必深入
|
c********t
发帖数: 5706 | 12 没人理，发现原题桥长100+，lz给的10^9，自己优化了一下空间。 BTW, 小青蛙肯定累
死在桥中间了。
public int frogJump2(int bridgeLength, int s, int t, int m,
HashSet stones) {
int[] dp = new int[t];
for (int i = s; i <= t; i++) {
if (stones.contains(i))
dp[i-1] = 1;
}
for (int i = t; i < bridgeLength; i++) {
int index = i%t;
int prev_stones = Integer.MAX_VALUE;
for (int j = s; j <= t; j++) {
prev_stones = Math.min(prev_stones, dp[j-1]);
}
dp[index] = prev_stones;
if (stones.contains(i))
dp[index]++;
}
return dp[(bridgeLength-1)%t];
}
【在 c********t 的大作中提到】
: 写了一个，大侠看看对不对，有没有什么可以优化的。
: public int frogJump(int bridgeLength, int s, int t, int m,
: HashSet stones) {
: int[] dp = new int[bridgeLength + 1];
: for (int i = s; i <= t; i++) {
: if (stones.contains(i))
: dp[i] = 1;
: }
: for (int i = t + 1; i <= bridgeLength; i++) {
: int prev_stones = Integer.MAX_VALUE;
|
s*****r
发帖数: 108 | 13 原题桥长就是 10^9 只是很多网页上显示成了 109
noip 是要求 1s 内出解的 大概 10^7 的算法才行 loop 到 10^9 是肯定超时的
其实题目暗示挺明显了 这么长的桥才这么少石子 通过这个条件优化时间的
【在 c********t 的大作中提到】
: 没人理，发现原题桥长100+，lz给的10^9，自己优化了一下空间。 BTW, 小青蛙肯定累
: 死在桥中间了。
: public int frogJump2(int bridgeLength, int s, int t, int m,
: HashSet stones) {
: int[] dp = new int[t];
: for (int i = s; i <= t; i++) {
: if (stones.contains(i))
: dp[i-1] = 1;
: }
: for (int i = t; i < bridgeLength; i++) {
|
c********t
发帖数: 5706 | 14 好像明白了，是直接判断有多少个连续长度超过T的石子路段？
【在 s*****r 的大作中提到】
: 原题桥长就是 10^9 只是很多网页上显示成了 109
: noip 是要求 1s 内出解的 大概 10^7 的算法才行 loop 到 10^9 是肯定超时的
: 其实题目暗示挺明显了 这么长的桥才这么少石子 通过这个条件优化时间的
|
