jianminchen/Chinese version of dynamic programming

## Chinese version of dynamic programming
Read a dynamic programming blog:

http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml

什么是动态规划，我们要如何描述它?

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。
使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

现在让我们通过一个例子来了解一下DP的基本原理。

首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

“状态”代表什么及如何找到它?

“状态"用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚，跳过直接上例子。

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用
贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)

首先我们思考一个问题，如何用最少的硬币凑够i元( i < 11 )？为什么要这么问呢？
两个原因：
1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。
2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同
一个问题(规模变小后的问题其实是原问题的子问题)。

好了，让我们从最小的 i 开始吧。当 i = 0，即我们需要多少个硬币来凑够 0 元。由于1，3，5都大于0，
即没有比 0 小的币值，因此凑够 0 元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有
利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够 0 元我们最少需
要0个硬币。”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。那么，我们用
d(i) = j 来表示凑够 i 元最少需要 j 个硬币。

于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。

当i = 1 时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够 0 元即
可，而这个是已经知道答案的，即d(0) = 0。所以，d(1) = d(1-1) + 1 = d(0) + 1 = 0 + 1 = 1。

当i=2时，仍然只有面值为 1 的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2 - 1 = 1
元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以
d(2) = d(2-1) + 1 = d(1) + 1 = 1 + 1 = 2。
一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为 1 的硬
币！

耐心点，让我们看看 i = 3 时的情况。当i = 3 时，我们能用的硬币就有两种了：1元的和3元的( 5元的
仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了
一个1元的硬币，我的目标就变为了：凑够3 - 1 = 2 元需要的最少硬币数量。即
d(3) = d(3-1)+1=d(2)+1=2+1=3。
这个方案说的是，我拿 3 个 1 元的硬币；

第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即
d(3)=d(3-3)+1=d(0)+1=0+1=1.
这个方案说的是，我拿1个3元的硬币。

好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？
具体是这样得到的：d(3) = min{d(3-1)+1, d(3-3)+1}。

OK，码了这么多字讲具体的东西，让我们来点抽象的。从以上的文字中，我们要抽出动态规划里非常
重要的两个概念：状态和状态转移方程。

上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，这个状态是怎么找出来
的呢？

我在另一篇文章 动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也
就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个
硬币。那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包
含状态d(i)的方程是：d(3) = min{d(3-1) + 1, d(3-3) + 1}。没错，它就是状态转移方程，描述状态
之间是如何转移的。当然，我们要对它抽象一下，
d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
有了状态和状态转移方程，这个问题基本上也就解决了。当然了，Talk is cheap,show me the code!
	Read a dynamic programming blog:

	http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml

	什么是动态规划，我们要如何描述它?

	动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。
	使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

	现在让我们通过一个例子来了解一下DP的基本原理。

	首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。

	“状态”代表什么及如何找到它?

	“状态"用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚，跳过直接上例子。

	如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用
	贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)

	首先我们思考一个问题，如何用最少的硬币凑够i元( i < 11 )？为什么要这么问呢？
	两个原因：
	1.当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。
	2.这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同
	一个问题(规模变小后的问题其实是原问题的子问题)。

	好了，让我们从最小的 i 开始吧。当 i = 0，即我们需要多少个硬币来凑够 0 元。由于1，3，5都大于0，
	即没有比 0 小的币值，因此凑够 0 元我们最少需要0个硬币。 (这个分析很傻是不是？别着急，这个思路有
	利于我们理清动态规划究竟在做些什么。) 这时候我们发现用一个标记来表示这句“凑够 0 元我们最少需
	要0个硬币。”会比较方便，如果一直用纯文字来表述，不出一会儿你就会觉得很绕了。那么，我们用
	d(i) = j 来表示凑够 i 元最少需要 j 个硬币。

	于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。

	当i = 1 时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够 0 元即
	可，而这个是已经知道答案的，即d(0) = 0。所以，d(1) = d(1-1) + 1 = d(0) + 1 = 0 + 1 = 1。

	当i=2时，仍然只有面值为 1 的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2 - 1 = 1
	元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。所以
	d(2) = d(2-1) + 1 = d(1) + 1 = 1 + 1 = 2。
	一直到这里，你都可能会觉得，好无聊，感觉像做小学生的题目似的。因为我们一直都只能操作面值为 1 的硬
	币！

	耐心点，让我们看看 i = 3 时的情况。当i = 3 时，我们能用的硬币就有两种了：1元的和3元的( 5元的
	仍然没用，因为你需要凑的数目是3元！5元太多了亲)。既然能用的硬币有两种，我就有两种方案。如果我拿了
	一个1元的硬币，我的目标就变为了：凑够3 - 1 = 2 元需要的最少硬币数量。即
	d(3) = d(3-1)+1=d(2)+1=2+1=3。
	这个方案说的是，我拿 3 个 1 元的硬币；

	第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即
	d(3)=d(3-3)+1=d(0)+1=0+1=1.
	这个方案说的是，我拿1个3元的硬币。

	好了，这两种方案哪种更优呢？记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？
	具体是这样得到的：d(3) = min{d(3-1)+1, d(3-3)+1}。

	OK，码了这么多字讲具体的东西，让我们来点抽象的。从以上的文字中，我们要抽出动态规划里非常
	重要的两个概念：状态和状态转移方程。

	上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，这个状态是怎么找出来
	的呢？

	我在另一篇文章动态规划之背包问题(一)中写过：根据子问题定义状态。你找到子问题，状态也
	就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个
	硬币。那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包
	含状态d(i)的方程是：d(3) = min{d(3-1) + 1, d(3-3) + 1}。没错，它就是状态转移方程，描述状态
	之间是如何转移的。当然，我们要对它抽象一下，
	d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
	有了状态和状态转移方程，这个问题基本上也就解决了。当然了，Talk is cheap,show me the code!