基本思想：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。
例子(leetcode-322)：
解题思路：
对于每个金额，使用变量j遍历面值coins数组
public int CoinChange(int[] coins, int amount)
{
//定义一个数组，数组下标表示金额值(从0到amount),数据存放每种金额值所需的最少硬币个数(数组长度为amount+1,从0元开始)
//例如amount=6,下标是: 0, 1, 2, 3, 4, 5, 6 , dp[6]表示下标为6元时所需的最少硬币个数（既dp[i]是最优解）
int[] dp = new int[amount + 1] ;
dp[0] = 0;
//数组1开始全部初始化为-1
for (int i = 1; i < dp.Length; i++)
{
dp[i] = -1;
}
//首先遍历数组dp,i既表示金额值，从1开始
for (int i = 1; i < dp.Length; i++)
{
//其次遍历面值集合coins
for (int j = 0; j < coins.Length; j++)
{
//dp[i-coins[j]]是重点，dp[i-coins[j]]表示i金额减去每次遍历的coins[j]面额，剩下的取 min{ dp[i-coins[j]] } 最小值
//例如i=6,面值有1，2，5，7元，首先遍历面值为1，dp[i-coins[j]]表示拿一个1元出来，剩下5元，5元最优解是dp[5]，是已知的；
//同理，再遍历2，剩dp[4]；遍历5，剩dp[1],则求 min{dp[6-1],dp[6-2],dp[6-5]}，其中最小的值加1就是当前金额i的最优解
if (i>=coins[j] && dp[i-coins[j]]!= -1 )//找出比i小的面值,且dp[i]的前面dp[比i小的]不能是-1
{
if (dp[i]==-1 || dp[i] > dp[i-coins[j]]+1)
{
dp[i] = dp[i - coins[j]]+1;
}
}
}
}
return dp[amount];
}
总结：不管子问题以后是否被用到，只要它被计算过，就将其结果填入表中(可能之后会用到子问题结果，这样就不用再重复计算了，降低时间复杂度，用空间交换时间)。这就是动态规划法的基本思路。
