动态规划——从入门到高级

动态规划

recurrent formula：递推公式
polynomial complexity：多项式复杂度

前言

原文：《Dynamic Programming – From Novice to Advanced》

在我们遇到的问题中，有很大一部分可以用动态规划（Dynamic Programming——DP）来解决。解决这类问题能够很大幅度提升你的技能与能力。我会试着帮你理解如何使用DP来解决问题。这篇文章围绕实例展开，因为生硬的理论很难理解。

Note:如果你对某一节内容已经了解并且感到无聊，你可以直接跳过。

简介（入门）

什么是动态规划，如何描述动态规划？

动态规划是一类基于一个或多个初始状态和递推公式的算法。当前问题的一个子问题可以由先前的问题递推得到。使用动态规划的时间复杂度是个多项式，因此它比回溯法（backtracking）和暴力法（brute-force）等快很多。

现在我们通过一个实例来看看动态规划的基本原理：

给定 N 枚面值分别是V1, V2 ...... VN 的硬币和总价值 S，求最少用多少枚可以凑足 S（每种面值的硬币有无限个），如果不能正好凑足 S 输出 -1。

现在我们来构造动态规划的解法：：
首先，我们需要找到某个状态（state）的最优解，并且同个当前状态的最优解可以递推出下个状态的最优解。

“状态” 代表什么？
“状态”用来描述当前问题和子问题的解。例如：定义某个“状态”表示凑足总价值 i (i<=s) 的解。定义另一个小规模的状态表示凑足总价值 j (j < i) 的解。为了找到状态 i，我们需要找到所有较 i 小的状态 j（j < i）。如果已经找到状态 i 最优解，那么我们能很容易的找到下一个状态——总价值 i+1的解。

如何找到 “状态”？
很简单——对于每种硬币 j，Vj <= i, 找到总价值 i-Vj 所需要的最小硬币数（我们之前已经找到了）记为 m，如果m+1比我们之前找到的总价值i的最优解更小，那么更新最优解。

为了更好的理解上面的话，我们举个例子：
给定面值 1，3，5的硬币和总价值 S=11.

定义 dp[i]=j 表示凑足总价值 sum=i 时最少需要 j 枚硬币
首先，我们标记状态 0(dp[0]) —— sum=0 时最优解为0。然后我们寻找状态 1（dp1 —— sum=1时的解）。首先，给状态 1 设置一个初始值inf（一个很大的值）。然后我们发现第一枚硬币面值V1小于或等于当前的sum。然后我们继续分析，发现 dp[1-V1]=0，因为我们要在sum=1-V1的基础上加一枚硬币，所以 dp1=1。