Dynamic Programming是刷Leetcode当中很重要的一道关卡。阅读了知乎以及一些科技blog之后对于动态规划还是一知半解。终于自己刷了几道题之后有了一些体会,所以记录在此。不敢说专业准确,只是“纸上得来终觉浅,觉知此事要躬行”
DP适用题目
DP 适用题目对我来说有两个特征:
- 有子问题:不管是用递归还是循环,最终求解问题都应该能被拆解成求解子问题,in other words,可以得出状态递推方程。
- 有“讨价还价”的过程:也可以说成是有重叠状态,需要剪枝。例如1,3,5硬币求得10等的问题,以及类似的0-1背包问题,都涉及到重叠状态,用brutal force 或者greedy会有重叠或者次优解优先于最优解的情况。所以,面对这种需要
网友评论