动态规划
动态规划不是魔法,它也是通过暴力方法尝试答案,只是方式更加 “聪明”,使得实际上时间复杂度并不高。
动态规划与暴力、回溯算法的区别
上面这句话也说明了,所有动态规划问题都能通过暴力方法解决!是的,所有最优解问题都可以通过暴力方法尝试(以及回溯算法),最终找出最优的那个。
暴力算法几乎可以解决一切问题。回溯算法的特点是,通过暴力尝试不同分支,最终选择结果最优的线路。
而动态规划也有分支概念,但不用把每条分支尝试到终点,而是在走到分叉路口时,可以直接根据前面各分支的表现,直接推导出下一步的最优解!然而无论是直接推导,还是前面各分支判断,都是有条件的。动态规划可解问题需同时满足以下三个特点:
1.存在最优子结构。
2.存在重复子问题。
3.无后效性。