【Leetcode】二十、记忆化搜索：零钱兑换

1、记忆化搜索

也叫备忘录，即把已经计算过的结果存下来，下次再遇到，就直接取，不用重新计算。目的是以减少重复计算。

以前面提到的斐波那契数列为例，计算F(5)，拆成F(4) + F(3)，接下来递归的顺序，如上图红色箭头，会先算左侧一支，计算完F(4)后，函数往下接着执行，才计算右侧一支的F(3)

可以发现，计算左侧一支的F(4)时，会得到F(3)的值，存下F(3)的值的话，执行到右侧一支计算F(3)时，直接取就行。

考虑初始化一个数组，数组元素为一个题目中不可能出现的值。然后将F(0)存在数组下标为0的地方，F(3)存数组下标为3的地方，计算一个值时，先在数组中找，找不到时再计算。

2、leetcode509：斐波那契数列

用一个int数组，存储计算过的每个F(x)，方便后面使用

public class P509Two {public int recursion(int n) {//F(0)和F(1)if (n < 2) {return n == 0 ? 0 : 1;}int[] dp = new int[n + 1];dp[1] = 1;  //F(1)// 根据方程式，计算每个值，存入数组，从F(2)一路计算到F(5)for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

当然，这儿也是动态规划。至于二者的在这块儿的区别参考前一篇的爬楼梯那题。动态规划，重在状态转移，那些不用的中间值，存不存在你。记忆化搜索则重在存储已计算结果的方式来避免重复计算。

3、leetcode322：零钱兑换

总金额amount恰好等于硬币面值时，最优解为1：

考虑利用等于硬币面值金额的最优解，推出其他金额的最优解。选择一个面值小于 总金额amount 的硬币之后，剩余金额对应的最优解是已知的，选择这些剩余金额最优解中最小的，再加上对应的那张面值小于i 的硬币，就是总金额amount的最优解。

如上，amount = 3，面值小于amount的硬币有面值为1和面值为2的：

• 如果选择面值为1的，剩余3 - 1 = 2，而2的最优解就是1，那amount的最优解就是 1 + 1 = 2
• 如果选择面值为2的，剩余3 - 2 = 1，而1的最优解就是1，那amount的最优解就是 1 + 1 = 2

因此，amount的最优解是2。如此，amount = 已知面值时，也可以这样推出来，比如amount = 2。同理：

amount = 14的剩余金额中，剩余7时，最优解最小，为1，因此14最优解就是 1 + 1 = 2。以amount14为例，初始化一个amount + 1的dp数组：

根据上面的分析，14有五种写法，选择最小值返回即可：

假设硬币面值有c1、c2、c3，那动态规划的状态转移方程式为：

F(amount) = Min（F(amount - c1) + F(amount - c2) + F(amount - c3)） + 1

有点像动态规划-完全平方数那题。实现（动态规划）：

public class P322 {public int coinChange(int[] coins, int amount) {if (null == coins || coins.length == 0) {return 0;}int[] dp = new int[amount + 1];// 填充-1Arrays.fill(dp, -1);// 金额0的最优解dp[0] = 0;for (int i = 1; i <= amount; i++) {// 对于每个金额i，遍历面值集合coinsfor (int coin : coins) {// 如果面值小于等于总金额i，并且剩余金额有最优解if (coin <= i && dp[i - coin] != -1) {// 如果总金额i没有计算过，或者，总金额i的最优解比正在计算的最优解大if (dp[i] == -1 || dp[i] > dp[i - coin] + 1) {// 更新最优解dp[i] = dp[i - coin] + 1;}}}}return dp[amount];}
}