动态规划算法基本思想
概念
动态规划（Dynamic Programming)算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许多。
现在通过一个例子来了解一下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。(括号内 1-1 表示当前要凑的钱数减掉当前面值后仍需要凑的钱数，可由前面的 d(x) 获得）
当 i=2 时，仍然只有面值为 1 的硬币可用，于是拿起一个面值为 1 的硬币， 接下来只需要再凑够 2-1=1 元即可(记得要用最小的硬币数量)，而这个答案也已经知道了。 所以 d(2)=d(2-1)+1=d(1)+1=1+1=2。
看看 i=3时的情况。当 i=3 时，我们能用的硬币就有两种了：1 元的和 3 元的(5 元的仍然没用，因为你需要凑的数目是3元！)。 既然能用的硬币有两种，我就有两种方案:
- 如果我拿了一个 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,d(i-1)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
java代码实现
//n:需要凑齐多少钱
public String dp(int n) {
n++;//从0元开始，所以需要加1
int[] min = new int[n];
int[] v = {1,3,5};
min[0] = 0
for(int i=1;i<n;i++) {
min[i] = min[i-1]+1;//默认情况下为上一种情况再加1块钱硬币
for(int j=0;j<v.length;j++) {
if(v[j] >i) {
break;
}
if(min[i-v[j]] < min[i-1]) {
//减去当前面值后所需硬币数量+1个当前面值的硬币
min[i] = min[i-v[j]] +1;
}
}
}
return min[n-1];
}
参考文章：