MagicLen

标签

动态规划

动态规划的观念与实战,先说明它适合处理哪些有重叠子问题的情境,再以 0/1 背包与找零钱为例,示范如何创建状态表并写出多种编程语言的解法。

共 3 篇文章

用动态规划解决问题:基本观念(有重叠子问题的问题)

动态规划(Dynamic Programming,简称 DP)是一种解决问题的技巧,主要被用来优化那些「记不住自己过去曾解出来的答案所以只好重复再解」的算法,让它们可以「记忆」已经找出来的答案,从而不断利用,以大大降低时间复杂度(从指数级降到线性)。