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

不废话了，前因后果可以到前一篇  看。

⋯⋯好吧，多废话一句 :-p 觉得这篇文章有用的话，你可以做两件事给楼主一些正反馈：

• 给代码所在 repo 加星 ()
• 给这篇文章加米
  

Unique Paths 是我入门动态规划的第一题，后来做面经做完这些 Follow-ups 才感觉自己真正懂了动态规划，特别是遍历顺序和空间优化。这篇文章总结 Unique Paths 的 Follow-ups，题目如下，从 地里的面经/glassdoor 搜集来之后，我又重新理了一遍语序。

给定一个矩形的宽和长，求所有可能的路径数量

Rules：
1. 从左上角走到右上角
2. 要求每一步只能向正右、右上或右下走，即 →↗↘

followup1: 优化空间复杂度至 O(n)
followup2: 给定矩形里的三个点，判断是否存在遍历这三个点的路经
followup3: 给定矩形里的三个点，找到遍历这三个点的所有路径数量
followup4: 给定一个下界 (x == H)，找到能经过给定下界的所有路径数量 (x >= H)
foll

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

吧既然提到了，再多说一些好了。这篇贴子 () 里歪楼的点就在于用了 “见不得光” 这个词，这带有一种偷偷摸摸的暗示，但还真的没有什么偷偷摸摸的，结合场景来看好了。

面试官喜欢的套路各种各样，有的不喜欢废话，多废话一句就是扣分项，有的希望你多说，少说了就是难相处，有的希望你多用 build-in 方法，说是考察你对语言的熟悉程度，有的希望你能自己实现 build-in 方法，不自己实现就是扣分项。

所以才说面试一定要沟通，而且很大程度靠运气，事前真是猜不透，在这种不确定的情况，希望能把握确定的东西是人性。以致于去面试当然希望能碰到自己熟悉的东西，熟悉的东西才能放心换着套路玩，于是形成刷题这种风气吧。

如果被问有没有做过题，不用见不得光，但你得知道，如果是程序以外的问题，你可以不用回答非黑即白的答案。

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

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

变斜体了，中间 \[i\] 忘记 escape 233

楼主想问一下follow up2的test case，为什么(3, 3, [[1, 0], [2, 1], [1, 2]])这一组返回False？ 这一组应该是可行的吧？

lz真的🐂🍺

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

blactangeri 发表于 2018-5-30 09:01
lz真的🐂🍺

虽然看不懂，我就当称赞啦，多谢～

jaychsu 发表于 2018-5-30 02:13
...

啊我理解错题意了，我以为可以从这三个点中任意一个点出发，其实还是从左上角走到右上角，但要经过三个点对吧？所以path一共是要经过5个点，要计算四次斜率对吧？很谢谢楼主！我不太懂python代码没看太懂！

谢谢楼主分享了！DP这个东西真的是虽然核心都是reduction，但每个人都有不同的approach，楼主写得很有启发性！