什么是动态规划

什么是动态规划

动态递推 ： 分治+ 最优子结构

将一个复杂的问题拆分成简单的子问题

与递归、分治有啥区别

没有本质区别，关键是看有无最优子结构， 如果没有最优子结构则需要计算所有的分支过程

共性

找到重复子问题

差异性

最优子结构、中间可以淘汰次优解