从 Unique Paths 的 Follow-ups 看动态规划的遍历和优化

谢谢楼主分享！！！

请教一下楼主：
https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/other/unique_paths_with_followups.py#L168
这里的i在什么时候会大于等于k呢？

楼主牛皮！！！我等小白的救星！！紫薯紫薯紫薯

hreat 发表于 2018-11-7 03:57
楼主牛皮！！！我等小白的救星！！紫薯紫薯紫薯

夸张了 lol，谢谢你的喜欢

klepht 发表于 2018-10-21 13:49
请教一下楼主：
https://github.com/jaychsu/algorithm/blob/c6f6c8e81aad557b8bc520b1a9298d201462c20f/o ...

抱歉啊，现在才看到。

因为只能向正右、右上或右下走，即 →↗↘。所以从第二动开始，y 至少是 1。所以如果第二动还是 0，那肯定就是不合法的路径。

代码里面这边我印象中我是只处理当全部 points 的 y 都为 0 的情况，因为如果第二动 ~ 最后一动之间有为 0 的，下面代码会覆盖到这种情况。

当全部 points 的 y 都为 0 的情况，可以参考下面。所有点都在 col1 上，自然也不可能是合法路径了。

1. y 0 1 2
   
2. x
   
3. 0  p
   
4. 1  q
   
5. 2  
   
6. 3  r

复制代码

unique path

楼主请问follow up1,为什么是返回dp[0], 而不是dp[m- 1]呢？不是要到右下角吗

hitnoah 发表于 2019-1-8 03:49
楼主请问follow up1,为什么是返回dp[0], 而不是dp[m- 1]呢？不是要到右下角吗

没有喔，f1~f4 是左上到右上，每一步往右(上中下)走。f5 是 从左上到左下，每一步往下(左中右)走。你可以试下题目要改成怎样才需要返回 dp[m - 1]，followup 常常也就拍脑袋想出来的 lol

问一下 follow up3 的case 对应 githhub line 146:     ((8, 6, [[0, 0], [0, 5], [0, 4]]), 9), 这个结果我算了下是4 可否问下怎么算出来9 吗， 我有注意非经过点全部清零

ihudada 发表于 2019-1-24 13:45
问一下 follow up3 的case 对应 githhub line 146:     ((8, 6, [[0, 0], [0, 5], [0, 4]]), 9), 这个结果 ...

空白的是 0 或是不可能经过指定点的位置，`| |` 包起来的是指定点

1.   j 0 1 2 3 4 5
   
2. i
   
3. 0  |1|1 2 4|9|9|
   
4. 1     1 2 5
   
5. 2       1
   
6. 3
   
7. 4
   
8. 5
   
9. 6
   
10. 7

复制代码