动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来，如果以后在求解较大子问题的时候需要用到这些子问题的解，就可以直接取出这些已经计算过的解而免去重复运算。保存子问题的解可以使用填表方式，例如保存在数组中。
用一个实际例子来体现动态规划的算法思想——硬币找零问题。
问题描述:
假设有几种硬币，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。例如几种硬币为[1, 3, 5], 面值2的最少硬币数为2(1, 1), 面值4的最少硬币数为2(1, 3), 面值11的最少硬币数为3(5, 5, 1或者5, 3, 3).
问题分析:
假设不同的几组硬币为数组coin[0, ..., n-1]. 则求面值k的最少硬币数count(k), 那么count函数和硬币数组coin满足这样一个条件:
count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;
并且在符合条件k - coin[i] >= 0 && k - coin[i] < k的情况下, 前面的公式才成立.
因为k - coin[i] < k的缘故, 那么在求count(k)时, 必须满足count(i)(i <- [0, k-1])已知, 所以这里又涉及到回溯的问题.
所以我们可以创建一个矩阵matrix[k + 1][coin.length + 1], 使matrix[0][j]全部初始化为0值, 而在matrix[i][coin.length]保存面值为i的最少硬币数.
而且具体的过程如下:
* k|coin 1 3 5 min * 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2 * ...
