DP的内在逻辑

本人数学专业，想跳槽大厂，但因为刷题不够吃了几个拒信，目前正在恶补。动态规划这一块感觉属于难题比较集中的一块。感觉在压力条件下快速构思一个正确的方案还是不能完全做到。希望得到大家的分享和指导。

目前我感觉DP和数学归纳法（Induction）有很多相通之处。Induction证明某个命题通过：1，前几项成立；2，递推关系成立；来证明一般项成立。感觉DP的内在逻辑跟这个很像，只不过Induction是证明一般项成立，DP是直接用来求解一般项。感觉Medium的DP题按照这个思路去想还是经常能够摸到一点思路。

抛砖引玉，不知我这个思路对不对。

基本就是一回事 证明题给了状态空间 难在写出状态转移方程 而编程题一般是难在写出状态空间 状态转移方程在合适的状态空间下比较显然

小弟认为，dp的就是是recursion+memoization/tabulation。所以，dp很像recursion，很像induction，楼主说的有道理。

归纳法思考时是小到大，证明也是。
DP思考时是大到小，求解时是小到大。

个人理解

补充内容 (2022-01-09 03:28 +08:00):
也不对，dp取决于是top down还是bottom up，前者是大到小写代码，后者是小到大写代码。

撸代码去了，临时琢磨的

Induction像recursion多一些

Induction is often used to prove DP correctness.

babybear68 发表于 2022-01-08 13:57:23
基本就是一回事 证明题给了状态空间 难在写出状态转移方程 而编程题一般是难在写出状态空间 状态转移方程在合适的状态空间下比较显然

很有道理，DP写出状态空间是关键