目录
动态规划（Dynamic Programming）
动态规划，简称DP
是求解最优化问题的一种常用策略
通常的使用套路（一步一步优化）
① 暴力递归（自顶向下，出现了重叠子问题）
② 记忆化搜索（自顶向下）
③ 递推（自底向上）
找零钱
假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
此前用贪心策略得到的并非是最优解（贪心得到的解是 5 枚硬币）
假设 dp(n) 是凑到 n 分需要的最少硬币个数
如果第 1 次选择了 25 分的硬币，那么 dp(n) = dp(n – 25) + 1
如果第 1 次选择了 20 分的硬币，那么 dp(n) = dp(n – 20) + 1
如果第 1 次选择了 5 分的硬币，那么 dp(n) = dp(n – 5) + 1
如果第 1 次选择了 1 分的硬币，那么 dp(n) = dp(n – 1) + 1
所以 dp(n) = min { dp(n – 25), dp(n – 20), dp(n – 5), dp(n – 1) } + 1
一、暴力递归
暴力递归（自顶向下的调用，出现了重叠子问题）
+(int)coins:(int)n{
if (n < 1) return INT_MAX;//
//可选的硬币大小为 25 20 5 1
if (n == 25 || n == 20 ||n == 5 ||n == 1 ) return 1;
/**
凑够零钱n，最后一次拿的肯定是 1 5 20 25中的一个
所以求出 凑够 n-1 n-5 n-20 n-25 需要的最少硬币个数 加1，就是凑够n需要的硬币个数
在其中选出最小的，就是凑够n的最小的硬币数。
*/
int min1 = MIN([self coins:n-25], [self coins:n-20]);
int min2 = MIN([self coins:n- 5], [self coins:n- 1]);
return MIN(min1, min2)+1;
}
类似于斐波那契数列的递归版，会有大量的重复计算，时间复杂度较高
二、记忆化搜索
记忆化搜索（自顶向下的调用），将已经计算出的值进行存储，后续不再重复计算。
+(int)coins2:(int)n{
if (n < 1) return -1;
//dp[i]是凑够i分时的最少硬币个数，初始化为0
NSMutableArray * dp = [NSMutableArray arrayWithCapacity:n+1];
for (int i=0; i<n+1; i++) {
dp[i] = @(0);
}
NSArray * faces = @[@1,@5,@20,@25];
for (NSNumber* face in faces) {
if (n < face.intValue) break;
dp[face.intValue] = @(1);
}
return [self __coins2:n dp:dp];
}
+(int)__coins2:(int)n dp:(NSMutableArray*)dp{
if (n < 1) return INT_MAX;
//如果没有计算过，计算
if ([dp[n] intValue] == 0) {
int min1 = MIN([self __coins2:n-25 dp:dp], [self __coins2:n-20 dp:dp]);
int min2 = MIN([self __coins2:n- 5 dp:dp], [self __coins2:n- 1 dp:dp]);
dp[n] = @(MIN(min1, min2)+1);
}
//如果之前计算过，直接取出
return [dp[n] intValue];
}
三、递推（自底向上）
+(int)coins3:(int)n {
if (n < 1) return -1;
//dp[i]是凑够i分时的最少硬币个数
NSMutableArray * dp = [NSMutableArray arrayWithCapacity:n+1];
for (int i=0; i<n+1; i++) {
dp[i] = @(0);
}
/**
凑够零钱n，最后一次拿的肯定是 1 5 20 25中的一个
所以求出 凑够 n-1 n-5 n-20 n-25 需要的最少硬币个数 加1，就是凑够n需要的硬币个数
在其中选出最小的，就是凑够n的最小的硬币数。
*/
/**
由于是自底向上，求i的时候 i-1,i-5,i-20,i-25肯定已经有值了
*/
for (int i = 1; i <= n; i++) {
// int min = INT_MAX;
// if (i >= 1) min = MIN([dp[i - 1] intValue], min);
//上边两句可用下面一句代替
int min = min = [dp[i - 1] intValue];
if (i >= 5) min = MIN([dp[i - 5] intValue], min);
if (i >= 20) min = MIN([dp[i - 20] intValue], min);
if (i >= 25) min = MIN([dp[i - 25] intValue], min);
dp[i] = @(min + 1);
}
return [dp[n] intValue];
}
时间复杂度、空间复杂度：O(n)
通过上面的例子初步认识下动态规划，其实上面三步已经演示了动态规划是怎么来的。
四、输出具体方案
+(int)coins4:(int)n {
if (n < 1) return -1;
//dp[i]是凑够i分时的最少硬币个数
NSMutableArray * dp = [NSMutableArray arrayWithCapacity:n+1];
for (int i=0; i<n+1; i++) {
dp[i] = @(0);
}
//faces[i]是凑够i分时最后那枚硬币的面值
NSMutableArray * faces = [NSMutableArray arrayWithCapacity:n+1];
for (int i=0; i<n+1; i++) {
faces[i] = @(0);
}
for (int i = 1; i <= n; i++) {
int min = INT_MAX;
if (i >= 1 && [dp[i - 1] intValue]<min){
min = [dp[i - 1] intValue];
faces[i] = @(1);
}
if (i >= 5 && [dp[i - 5] intValue]<min){
min = [dp[i - 5] intValue];
faces[i] = @(5);
}
if (i >= 20 && [dp[i - 20] intValue]<min) {
min = [dp[i - 20] intValue];
faces[i] = @(20);
}
if (i >= 25 && [dp[i - 25] intValue]<min) {
min = [dp[i - 25] intValue];
faces[i] = @(25);
}
dp[i] = @(min + 1);
[self printN:i faces:faces];
}
return [dp[n] intValue];
}
//打印凑够n分，选择的硬币
+(void)printN:(int)n faces:(NSArray*)faces{
printf("[%d] = ",n);
while (n>0) {
int face = [faces[n] intValue];
printf("%d ",face);
n-=face;
}
printf("\n");
}
五、通用方案
/// 零钱兑换，返回最少硬币个数
/// @param n 找零
/// @param faces 硬币
+(int)coins5:(int)n faces:(nonnull NSArray *)faces{
if (n < 1 || faces == nil || faces.count == 0) return -1;
//dp[i]是凑够i分时的最少硬币个数
NSMutableArray * dp = [NSMutableArray arrayWithCapacity:n+1];
for (int i=0; i<n+1; i++) {
dp[i] = @(0);
}
for (int i = 1; i <= n; i++) {
int min = INT_MAX;
// 2 5 20 25
for (NSNumber* face in faces) {
int faceInt = face.intValue;
//i 比该枚硬币小不可选
if ( i < faceInt) continue;
int v = [dp[i-faceInt] intValue];
//v<0 dp[i-faceInt] 不可凑 不选
//v >= min 不是最小解 不选
if (v < 0 || v >= min) continue;
//最小解
min = v;
}
//如果最小值还是INT_MAX，证明无法凑够
if (min == INT_MAX) {
dp[i] = @(-1);
}else{
dp[i] = @(min + 1);
}
}
return [dp[n] intValue];
}
行者常至，为者常成！