有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。
给定数组 penny 及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
测试样例：
[1,2,4],3,3
返回：
2
Solutions
这个题目说是能够吧暴力搜索、记忆化搜索和动态规划串联起来了。
暴力搜索法
要搞清楚暴力搜索过程。
# -*- coding:utf-8 -*-
class Exchange:
def countWays(self, penny, n, aim):
# write code here
if penny is None or aim == 0:
return 0
return self.foo(penny, 0, aim)
def foo(self, arr, index, aim):
res = 0
if index == len(arr):
res = 1 if aim == 0 else 0
else:
for i in range(aim + 1):
if arr[index] * i > aim:
break
res += self.foo(arr, index + 1, aim - arr[index] * i)
return res
记忆化搜索法
我们可以看到在递归过程中，很有可能会出现重复计算的问题，那么我们通过空间换时间的办法，把递归时计算过的结果保存下来。
# 记忆化搜索法
import java.util.*;
public class Exchange {
public int countWays(int[] penny, int n, int aim) {
// write code here
if (penny == null || penny.length == 0 || aim <= 0)
return 0;
int [][] map = new int[penny.length+1][aim+1];
return process2(penny, 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;
}
}
我对照着用 Python 实现了一遍，就是有问题我勒个去啊！？
# -*- coding:utf-8 -*-
class Exchange:
def countWays(self, penny, n, aim):
# write code here
if penny is None or len(penny) == 0 or aim < 0:
return 0
row, col = len(penny) + 1, aim + 1
# dp = [[0] * col] * row
mp = [[0] * col for _ in range(row)]
return self.foo(penny, 0, aim, mp)
def foo(self, arr, index, aim, mp):
res = 0
if index == len(arr):
res = 1 if aim == 0 else 0
else:
for i in range(aim + 1):
if arr[index] * i > aim:
break
mp_val = mp[index + 1][aim - arr[index] * i]
if mp_val != 0:
res += 0 if mp_val == -1 else mp_val
else:
res += self.foo(arr, index + 1, aim - arr[index] * i, mp)
if res == 0:
mp[index][aim] = -1
else:
mp[index][aim] = res
return res
动态规划
记忆化过程其不规定计算顺序（不管状态路径），而动态规划严格规定计算顺序。先使用比较复杂的二维状态转移公式：
计算 dp[i][j] 时，需要所有取当前 i 面值货币张数的的所有情况累加。
import java.util.*;
public class Exchange {
public int countWays(int[] penny, int n, int aim) {
// write code here
if (penny == null || penny.length == 0 || aim <= 0)
return 0;
int [][] dp = new int[penny.length][aim+1];
for (int i = 0; i < penny.length; i++){
dp[i][0] = 1;
}
for (int j = 1; penny[0] * j <= aim; j++){
dp[0][penny[0] * j] = 1;
}
int num = 0;
for (int i = 1; i < penny.length; i++){
for (int j = 1; j <= aim; j++){
num = 0;
for (int k = 0; j - penny[i] * k >= 0; k++){
num += dp[i-1][j - penny[i] * k];
}
dp[i][j] = num;
}
}
return dp[penny.length-1][aim];
}
}
还是那样，用 Python 实现一遍就是错错错！！！找到错误的原因了……尼玛，原来是浅拷贝的原因。代码中注释的部分体现了动态规划的状态转移矩阵，自我体会一下这里表示的意思。
# -*- coding:utf-8 -*-
class Exchange:
def countWays(self, penny, n, aim):
# write code here
if penny is None or len(penny) == 0 or aim < 0:
return 0
row, col = len(penny), aim + 1
# dp = [[0] * col] * row
dp = [[0 for _ in range(col)] for _ in range(row)]
for i in range(len(penny)):
dp[i][0] = 1
for j in range(1, aim + 1):
if penny[0] * j > aim:
break
dp[0][penny[0] * j] = 1
for i in range(1, len(penny)):
for j in range(1, aim + 1):
# if j >= penny[i]:
# dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]
# else:
# dp[i][j] = dp[i - 1][j]
num = 0
k = 0
while j - penny[i] * k >= 0:
num += dp[i - 1][j - penny[i] * k]
k += 1
dp[i][j] = num
return dp[len(penny) - 1][aim]
然后是使用空间压缩，进一步优化得到更低的时间复杂度：
# -*- coding:utf-8 -*-
class Exchange:
def countWays(self, penny, n, aim):
# write code here
if penny is None or len(penny) == 0 or aim < 0:
return 0
# dp = [[0] * col] * row
dp = [0] * (aim + 1)
for j in range(0, aim + 1):
if penny[0] * j > aim:
break
dp[penny[0] * j] = 1
for i in range(1, len(penny)):
for j in range(1, aim + 1):
if j >= penny[i]:
dp[j] += dp[j - penny[i]]
return dp[aim]