通常的使用套路（一步一步优化） ① 暴力递归（自顶向下，出现了重叠子问题） ② 记忆化搜索（自顶向下） ③ 递推（自底向上）
1、动态规划的常规步骤
动态规划中的“动态”可以理解为是“会变化的状态” ① 定义状态（状态是原问题、子问题的解） ✓ 比如定义 dp(i) 的含义 ② 设置初始状态（边界） ✓ 比如设置 dp(0) 的值 ③ 确定状态转移方程 ✓ 比如确定 dp(i) 和 dp(i – 1) 的关系
2、动态规划的一些相关概念
来自*的解释 Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once , and storing their solutions. ① 将复杂的原问题拆解成若干个简单的子问题 ② 每个子问题仅仅解决1次，并保存它们的解 ③ 最后推导出原问题的解
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins(41));
}
/*暴力递归(自顶向下的调用，出现了重叠子问题)*/
static int coins(int n){
if (n < 1) return Integer.MAX_VALUE;
if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
int min1 = Math.min(coins(n - 25), coins(n - 20));
int min2 = Math.min(coins(n - 5), coins(n - 1));
return Math.min(min1,min2) + 1 ;
}
}
（2）找零钱 – 记忆化搜索
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins2(41));//3
System.out.println(coins2(19));//7
}
/*记忆化搜索(自顶向下的调用)*/
static int coins2(int n){
if (n < 1) return -1;//一开始就过滤掉不合理的条件
//数组dp存储凑到n分需要的最少硬币个数
int[] dp = new int[n + 1];
int[] faces = {1,5,20,25};
for (int face : faces) {
if (n < face) continue;
//凑够n分需要的最少硬币个数是1枚
dp[face] = 1;
}
return coins2(n,dp);
}
static int coins2(int n,int[] dp){
if (n < 1) return Integer.MAX_VALUE;//为了下面递归服务(递归基)
if (dp[n] == 0){
int min1 = Math.min(coins2(n - 25,dp), coins2(n - 20,dp));
int min2 = Math.min(coins2(n - 5,dp), coins2(n - 1,dp));
dp[n] = Math.min(min1,min2) + 1;
}
return dp[n];
}
}
（3）找零钱 – 递推
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins3(41));//3
System.out.println(coins3(19));//7
}
/*递推(自底向上)*/
static int coins3(int n){
if (n < 1) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = dp[i-1];
if (i >= 5) min = Math.min(dp[i-5], min);
if (i >= 20) min = Math.min(dp[i-20], min);
if (i >= 25) min = Math.min(dp[i-25], min);
dp[i] = min + 1;
}
return dp[n];
}
}
时间复杂度、空间复杂度：O(n)
（4）思考题：请输出找零钱的具体方案（具体是用了哪些面值的硬币）
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins4(41));//3
System.out.println("--------------");
System.out.println(coins4(19));//7
}
/*具体是用了哪些面值的硬币*/
static int coins4(int n){
if (n < 1) return -1;
int[] dp = new int[n + 1];
//faces[i]是凑够i分时最后选择的那枚硬币的面值
int[] faces = new int[dp.length];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
if (i >= 1 && dp[i-1] < min) {
min = dp[i-1];
faces[i] = 1;
}
if (i >= 5 && dp[i-5] < min) {
min = dp[i-5];
faces[i] = 5;
}
if (i >= 20 && dp[i-20] < min) {
min = dp[i-20];
faces[i] = 20;
}
if (i >= 25 && dp[i-25] < min) {
min = dp[i-25];
faces[i] = 25;
}
dp[i] = min + 1;
//print(faces,i);
}
print(faces,n);
return dp[n];
}
static void print(int[] faces,int n){
System.out.print("["+ n +"] = ");
//faces[n]指的是最后一枚硬币
//n - faces[n]指的是除了最后一枚硬币外，剩下要凑的钱
while (n > 0){
System.out.print(faces[n]+ " ");
n -= faces[n];
}
System.out.println();
}
}
运行结果：
[41] = 1 20 20
3
--------------
[19] = 1 1 1 1 5 5 5
7
（5）找零钱 – 通用实现
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins5(41, new int[]{1,5,20,25}));//3
}
static int coins5(int n,int[] faces){
if (n < 1 || faces == null || faces.length == 0) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int face : faces) {
if (i < face) continue;;
min = Math.min(dp[i-face],min);
//dp(41) = 凑够41需要最少的硬币数量
//dp(41 -1) = dp(40) = 凑够40需要最少的硬币数量
//dp(41 -5) = dp(36) = 凑够36需要最少的硬币数量
//dp(41 -20) = dp(21) = 凑够21需要最少的硬币数量
//dp(41 -25) = dp(16) = 凑够16需要最少的硬币数量
//min{dp(40) , dp(36) , dp(21) , dp(16) } + 1 ->求用到硬币数量最少的个数
}
dp[i] = min + 1;
}
return dp[n];
}
}
public class CoinChange {
public static void main(String[] args) {
System.out.println(coins5(41, new int[]{1,5,20,25}));//3
System.out.println(coins5(6, new int[]{5,20,25}));//-1
}
static int coins5(int n,int[] faces){
if (n < 1 || faces == null || faces.length == 0) return -1;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int min = Integer.MAX_VALUE;
for (int face : faces) {
if (i < face) continue;
int v = dp[i -face];
if (v < 0 || dp[i - face] >= min) continue;
min = dp[i-face];
}
if (min == Integer.MAX_VALUE){
dp[i] = -1;
}else {
dp[i] = min + 1;
}
}
return dp[n];
}
}