由Leetcode详解算法 之 动态规划（DP） (2)

对于每一个以节点i为根节点的树，F(i,n)实际上等于其左子树的G(nr)乘以其右子树的G(nl);
因为这相当于在两个独立集合中各取一个进行排列组合，其结果为两个集合的笛卡尔乘积

我们由此可以得到公式F(i,n) = G(i-1)*G(n-i)
从而得到G(n)的递归公式：
G(n) = ΣG(i-1)G(n-i)

算法实现 class Solution { public int numTrees(int n) { int[] G = new int[n+1]; G[0] = 1; G[1] = 1; for(int i = 2; i <= n; ++i){ for(int j = 1; j <= i; ++j){ G[i] += G[j - 1] * G[i - j]; } } return G[n]; } }

一个典型的“自底向上”的动态规划问题。
当然，由于通过递推公式可以由数学方法得到G(n)的计算公式，直接使用公式求解也不失为一种方法。

Coin Change （Top-down）

322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
coins数组表示每种硬币的面值，amount表示钱的总数，若可以用这些硬币可以组合出给定的钱数，则返回需要的最少硬币数。无法组合出给定钱数则返回-1。

算法思路

1、首先定义一个函数F(S) 对于amount S 所需要的最小coin数
2、将问题分解为子问题：假设最后一个coin面值为C 则F(S) = F(S - C) + 1
S - ci >= 0 时，设F(S) = min[F(S - ci)] + 1 (选择子函数值最小的子函数，回溯可得到总体coin最少)
S == 0 时，F(S) = 0;
n == 0 时，F(S) = -1

算法实现 class Solution { public int coinChange(int[] coins, int amount) { if(amount < 1) return 0; return coinChange(coins, amount, new int[amount]); } private int coinChange(int[] coins, int rem, int[] count) { if(rem < 0) return -1; if(rem == 0) return 0; if(count[rem - 1]!=0) return count[rem - 1]; //这里的rem-1 其实就相当于 rem 从 0 开始计数(不浪费数组空间) int min = Integer.MAX_VALUE; //每次递归都初始化min for(int coin : coins){ int res = coinChange(coins, rem - coin, count); //计算子树值 if(res >= 0 && res < min) min = 1 + res; //父节点值 = 子节点值+1 （这里遍历每一种coin之后得到的最小的子树值） } count[rem - 1] = (min == Integer.MAX_VALUE) ? -1:min; //最小值存在count[rem-1]里，即这个数值(rem)的最小钱币数确定了 return count[rem-1]; } }

算法采用了动态规划的“自顶向下”的方式，使用了回溯法(backtracking)，并且对于回溯树进行剪枝（coin面值大于amount时）。
同时，为了降低时间复杂度，将已计算的结果（一定面值所需要的最少coin数）存储在映射表中。

虽然动态规划是钱币问题的一般认为的解决方案，然而实际上，大部分的货币体系（比如美元/欧元）都是可以通过“贪心算法”就能得到最优解的。

最后，如果大家对于文章有任何意见/建议/想法，欢迎留言讨论！