动态规划(dp)的总结

动态规划(dp)的总结
动态规划只要找到子问题，写起来就很简单，通常最多就二维dp数组即可解决问题，顶多再来个双dp，再加点逆向思维……下面列出我见过的子问题，别栽在dp上了，求求了。
能用dp做，首先得满足：你走这一步的结果不会影响到之前的结果。
其实也不提那么多了，只要看着差不多，都可以用dp试试。
直接顺序找到子问题就好
剑指 Offer II 088. 爬楼梯的最少成本
定义dp[i]为爬到i所需最少成本，dp[0]、dp[1]是边界，为0，状态转移：从下往上看每个阶梯，每个阶梯能从i-1或i-2上来，对应最少成本为：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])；最后返回dp.back()；

注：此题因为只用到了dp[i]、dp[i - 1]和dp[i - 2]，不如用res、pre和prepre存储，可以减

动态规划(dp)的总结最先出现在Python成神之路。