我们先从换钱问题说起。
问题描述：给定数组arr，arr中所有的值都为正数且不重复。每个值都代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。
这道题非常经典，可以用暴力搜索方法、记忆搜索方法、动态规划方法和化简后的动态规划方法来解决。而他们之间其实是有一个递推过程的，过程如下：
暴力搜索的方法描述如下
而剩下的[10, 25, 1]又可以 以[10]、[25，1]开始，如此，便会组成一个递归过程。那么定义如下的递归函数：
函数如下：
public class Test {
public int coins1(int[] arr, int aim){
if(arr == null || arr.length == 0 || aim < 0){
return 0;
}
return process1(arr, 0, aim);
}
public int process1(int[] arr, int index, int aim){
int res = 0;
if(index == arr.length){
res = aim == 0 ? 1 : 0; //如果最后一种钱都用完了都没使得aim为0，那么res就为0，否则为1
}else{
for(int i = 0; arr[index] * i <= aim; i++){
res += process1(arr, index + 1, aim - arr[index] * i);
}
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{5, 10, 25, 1};
int aim = 1000;
System.out.println(new Test().coins1(arr, aim));
}
}
暴力搜索之所以暴力，是因为存在着大量重复的计算。比如
下面是记忆搜索的方法：
记忆化搜索的方法最重要的是用一个hashmap存储已经计算的结果
而下面是经典的动态规划的方法：
下面我就将这三个方法放到一起对比:
public class Test {
//暴力递归
public int coins1(int[] arr, int aim){
if(arr == null || arr.length == 0 || aim < 0){
return 0;
}
return process1(arr, 0, aim);
}
public int process1(int[] arr, int index, int aim){
int res = 0;
if(index == arr.length){
res = aim == 0 ? 1 : 0; //如果最后一种钱都用完了都没使得aim为0，那么res就为0，否则为1
}else{
for(int i = 0; arr[index] * i <= aim; i++){
res += process1(arr, index + 1, aim - arr[index] * i);
}
}
return res;
}
//记忆化搜索
public int coins2(int[] arr, int aim){
if(arr == null || arr.length == 0 || aim < 0){
return 0;
}
//为什么要加1，因为后面存储的时候按照正常下标存，等于说第一行第一列不存东西
int[][] map = new int[arr.length + 1][aim + 1];
return process2(arr, 0, aim, map);
}
public int process2(int[] arr, int index, int aim, int[][] map){
int res = 0;
if(index == arr.length){
res = aim == 0 ? 1 : 0;
}else {
int mapValue = 0;
for(int i = 0; arr[index] * i <= aim; i++){
mapValue = map[index + 1][aim - arr[index] * i];
if(mapValue != 0){
res += mapValue == -1 ? 0 : mapValue;
}else{
res += process2(arr, index + 1, aim - arr[index] * i, map);
}
}
}
map[index][aim] = res == 0 ? -1 : res;
return res;
}
//动态规划
public int minCoins(int[] arr,int aim){
int[][] dp = new int[arr.length][aim + 1];
//初始状态
for(int i = 0; i < arr.length; i++)
dp[i][0]=1; //aim=0时
for(int j = 1;j <= aim; j++){ //第一行
int i = arr[0];
if(j % i==0)
dp[0][j]=1;
else
dp[0][j]=0;
}
//从上到下 从左到右
for(int i = 1; i < arr.length; i++){
for(int j = 1; j <= aim; j++){
if( j >= arr[i]){ //在前i-1项里面拼凑j，和在前i项里拼凑j-arr[i]--默认已经选择一个i
dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]];
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[arr.length - 1][aim];
}
public static void main(String[] args) {
int[] arr = new int[]{5, 10, 25, 1};
int aim = 1000;
System.out.println(new Test().coins1(arr, aim));
System.out.println(new Test().coins2(arr, aim));
System.out.println(new Test().minCoins(arr, aim));
}
}
动态规划的方法最重要的是这个转移矩阵，矩阵的最右下角的值为最终的结果，返回即可。动态规划与记忆化搜索都是以空间换时间，联系如下：
动态规划方法定义是：
虽然动态规划和记忆化搜索差不多，但是动态规划的结果存储是有顺序的，就让状态的优化称为可能。
而动态规划的关键点在于：
虽然动态规划有一系列的从暴力递归逐渐优化的过程，不过经典的动态规划，应该记住这些题。简而言之就是，动态规划的原理你得理解，但是题目记住题目就行，除非很牛逼可以现场了，否则面试的时候就是浪费时间。
这里非常感谢左神把动态规划讲的那么透彻，Respect！
