点击关注公众号，干货第一时间送达
咱们快刀斩乱麻，
不对，
咱们趁热打铁！
把上篇文章：数据结构和算法【20】零钱兑换
遗留的一个问题解决掉。
上篇文章给出了求解零钱兑换的方法，
但是，放在力扣上面超时了。
怎么加速？
（还是再看一眼题目吧，怕是有些小伙伴没有看过这道题）
一、各位，请听题
题例是：
题意算是很清晰的了，
上篇文章：数据结构和算法【20】零钱兑换 给出的解法是遍历判断数组每种面额的硬币，任意数量，凑齐金额。
暴力方法。
肯定能得到答案，
但是，需要每次都遍历一遍吗？
二、解题
我们看看上篇文章给出的递归方法：
方法可变参数只有两个， i 和 rest。
i 表示硬币数组coins 中的坐标，指第i+1个面额为 arr[i] 的硬币，初始化是0，
rest 表示当前需要凑齐的金额数，初始肯定是给定的 amount。
两个变量，能不能转换为二维表！！！
就像这样：
i 可以取值范围是 0 ~ coins.lenght 也就是 0 ~ N，
rest 可以取值范围是 0 ~ amount。
再看递归函数里面的 basecase：
如果 i == coins.lenght ，表示越界了，也就是没有硬币可选了，判断剩余金额rest
参照basecase，我们可以把二维表填上basecase的值：
除了 i = N，rest=0的时候，格子里面填0，其他的填上-1，表示无效解。
最后一行有值了，中间的呢？
我们再看：
如果当前遍历的到 dp[i][rest]，根据上篇文章给出的暴力递归方法，当前值是取决于 i+1 的结果集的，取里面的最小值：
就是 dp[i][rest] 取值是取决于 Min{dp[i+1][rest- n*coins[i]]}，
同样的，
dp[i][rest - coins[i]] 的值，也是取决于下一行Min{dp[i+1][rest- n*coins[i]]}
dp[i][rest - coins[i]] 是早于 dp[i][rest] 求解的，
当前来到 dp[i][rest]的时候，用之前已经求过的值，不就可以省很多事了！！！
结论就是：
dp[i][rest] 直接从左边的位置：dp[i][rest - coins[i]] 和 下边的位置：dp[i+1][rest] 取较小的那个即可。
最后的结果是哪个格子呢？
没有硬币可选，并且此时已经凑齐了amount金额的时候，
就是 dp[0][amount]
看看代码。
完整代码（改进版）：
public class CodingDemo {
/**
* TODO； 零钱兑换（改进版）
* @param coins
* @param amount
* @return
*/
public static int coinChange2(int[] coins, int amount) {
int N = coins.length;
//1，创建dp二维数组
int[][] dp = new int[N+1][amount+1];
//2，初始化 dp[N][1..amount] 为 -1
for (int i = 1; i <= amount; i++) {
dp[N][i] = -1;
}
//3, 填充dp表
//从下往上，从左往右
// N-1 -> 0 行
// 0 —> amount 列
for (int i = N-1; i >= 0 ; i--) {
for (int rest = 0; rest <= amount; rest++) {
//3.1 先给当前位置赋值为无效
dp[i][rest] = -1;
//3.2 判断同一列，下一行的数据是否有效
if (dp[i+1][rest] != -1){
dp[i][rest] = dp[i+1][rest];
}
//3.3 判断左侧位置是否有效，及剩余金额是否越界
if ( rest-coins[i] >= 0 && dp[i][rest-coins[i]] != -1 ){
//3.4 结合判断下方位置是否有有效，如果有效，取较小的那个
if (dp[i][rest] == -1){
dp[i][rest] = dp[i][rest-coins[i]] + 1;
} else {
dp[i][rest] = Math.min(dp[i+1][rest], dp[i][rest-coins[i]] + 1);
}
}
}
}
//返回答案
return dp[0][amount];
}
public static void main(String[] args) {
int[] arr = {1,2,5};
System.out.println(coinChange2(arr, 11));
}
}
输出：
D:\java\bin\java.exe
3
再去力扣试试水：
可以通过。
