动态规划(dynamic programming, DP)是一种将复杂问题分解成更小的子问题来解决的优化技术。动态规划和分而治之是不同的方法。分而治之方法是把问题分解成相互独立的子问题,然后组合它们的答案,而动态规划则是将问题分解成相互依赖的子问题。
用动态规划解决问题时,要遵循三个重要步骤:
(1) 定义子问题;
(2) 实现要反复执行来解决子问题的部分;
(3) 识别并求解出基线条件。
使用动态规划解决0-1背包问题代码:
1 | function knapsack(capacity, weights, values, n) { |
图示: