清华学霸总结的动态规划4步曲，仅这篇动归够了
九章算法《动态规划专题》金牌讲师
清华大学全国算法竞赛金牌，ACM国际大学生程序设计竞赛全球总决赛选手。FLAG资深面试官。
侯卫东的见面礼
FLAG高频动态规划66题
国内外大厂最新算法面试题
一线互联网公司真题解析
2020大厂面经汇总
礼包部分内容，长按扫码即可领取
4步套路，解决动态规划问题
// f(X)返回最少用多少枚硬币拼出X
int f(int X) {
// 0元钱只要0枚硬币
if (X == 0) return 0;
// 初始化用无穷大（为什么是正无穷？）
int res = MAX_VALUE;
// 最后一枚硬币是2元
if (X >= 2) {
res = Math.min(f(X – 2) + 1, res);
}
// 最后一枚硬币是5元
if (X >= 5) {
res = Math.min(f(X – 5) + 1, res);
}
// 最后一枚硬币是7元
if (X >= 7) {
res = Math.min(f(X – 7) + 1, res);
}
return res;
}
插入一下~
需要掌握的动态规划面试解题技巧还包括坐标型、位操型、序列型、博弈型、背包型、双序列以及一些高难面试题解。
本文篇幅有限无法逐一讲清，大家来白嫖我的在线分享吧（纯干货）。
白嫖方式：
长按扫码 — 跳转页面左下 —【免费试听】按钮即可👇
或点击最下方“阅读原文”
public int coinChange(int[] A, int M){
// A = [2,5,7]
// M = 27
int[] f = new int[M + 1];
int n = A.length; // 硬币的种类
// 初始化, 0个硬币
f[0] = 0;
// f[1], f[2], ... , f[27] = Integer.MAX_VALUE
for (int i = 1; i <= M; i++){
f[i] = Integer.MAX_VALUE;
}
for (int i = 1; i <= M; i++){
// 使用第j个硬币 A[j]
// f[i] = min{f[i-A[0]]+1, ... , f[i-A[n-1]]+1}
for (int j = 0; j < n; ++j){
// 如果通过放这个硬币能够达到重量i
if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {
// 获得i的重量的硬币数就可能是获得i-A[j]重量硬币数的方案+1
// 拿这个方案数量与原本的方案数打擂台，取最小值就行
f[i] = Math.min(f[i - A[j]] + 1, f[i]);
}
}
}
if (f[M] == Integer.MAX_VALUE){
return -1;
}
return f[M];
}
动态规划专题班 免费分享课
限时白嫖
长按扫码，点击免费报名即可
或点击下方“阅读原文”
白嫖戳这里