阿里算法工程师总结：动态规划4步曲，仅看这篇动归就够了

第二步，转移方程，把问题方程化。

====================

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}（动态规划都是要开数组，所以这里改用方括号表示）

实际面试中求解动态规划类问题，正确列出转移方程正确基本上就解决一半了。

但是请问：这与递归有什么不同？？

递归的解法：

// 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;

}

执行图如下：

要算f(27)，就要递归f(25)、f(22)、f(20)，然后下边依次递归……（三角形表示）。

问题明显——重复递归太多。

这是求f(27)，还可以勉强递归。如果求f(100)呢？简直是天文数字。最终结果就是递归超市。

求总体最值，一定优先考虑动态规划不要憨憨的去递归。

插入一下~

需要掌握的动态规划面试解题技巧还包括坐标型、位操型、序列型、博弈型、背包型、双序列以及一些高难面试题解。

本文篇幅有限无法逐一讲清，大家来白嫖我的在线分享吧（纯干货）。

第三步，按照实际逻辑设置边界情况和初始条件。

==========================

**【必做】**否则即使转移方程正确也大概率无法跑通代码。

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}的边界情况是[x-2]/[x-5]/[x-7]不能小于0（硬币面值为正），也不能高于27。

故对边界情况设定如下：

如果硬币面值不能组合出Y，就定义f[Y]=正无穷例如f[-1]=f[-2]=…=正无穷；f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正无穷,

**特殊情况：**本题的F[0]对应的情况为F[-2]、F[-5]、F[-7]，按照上文的边界情况设定结果是正无穷。

但是实际上F[0]的结果是存在的（即使用0个硬币的情况下），F[0]=0。可是按照我们刚刚的设定，F[0]=F[0-2]+1= F[-2]+1=正无穷。

岂不是矛盾？

这种用转移方程无法计算，但是又实际存在的情况，就必须通过手动定义。

这里手动强制定义初始条件为：F[0]=0.

而从0之后的数值是没矛盾的，比如F[1]= F[1-2]+1= F[-1]+1=正无穷（正无穷加任何数结果还是正无穷）；F[2]= F[2-2]+1= F[0]+1=1……

第四步，确定计算顺序并计算求解

===================

那么开始计算时，是从F[1]、F[2]开始呢？还是从F[27]、F[26]开始呢？

判断计算顺序正确与否的原则是：当我们要计算F[X]（等式左边，如F[10]）的时候，等式右边（f[X-2], f[X-5], f[X-7]等）都是已经得到结果的状态，这个计算顺序就是OK的。

实际就是从小到大的计算方式（偶有例外的情况我们后边再讲）。

例如我们算到F[12]的时候，发现F[11]、F[10]、F[9]都已经算过了，这种算法就是对的；而开始算F[27]的时候，发现F[26]还没有算，这样的顺序就是错的。

很显然这样的情况下写一个FOR循环就够了。

回到这道题，采用动态规划的算法，每一步只尝试三种硬币，一共进行了27步。算法时间复杂度（即需要进行的步数）为27*3。

与递归相比，没有任何重复计算。

**原题练习及实际代码：**这道题是lintcode编号669的Coin Change问题。代码如下：

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]);

}

}
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！

如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）

最后

由于篇幅原因，就不多做展示了
《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》，点击传送门即可获取！
Fd0U0o7-1712527198555)]

[外链图片转存中…(img-bB7wmAtV-1712527198556)]

[外链图片转存中…(img-JE3m1Mm0-1712527198556)]

[外链图片转存中…(img-NOCyYgVc-1712527198556)]

由于篇幅原因，就不多做展示了
《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》，点击传送门即可获取！