算法是一种艺术，给人感觉很不好接近，但是一旦你和ta熟络了，你就能发现这门艺术的内在是多么美妙且多变。
对于前端来说，算法也许不是最重要的，在日常工作中，几乎很少用到。所以很多人也不是很感冒。
不过呢，有句话这么说的：面试造火箭，上班拧螺丝。咱们得先学习造火箭，才能有拧螺丝的机会。
莫得办法，既然想要拧螺丝，就要有好活的老学到老的觉悟。否则连改锥都没了。
那么，看题。
给你一个表格，像这样的:
WX20191221-184813.png
从 (0, 0) 到 (M, N)移动，并假设，每次只能向下或者向右移动一步，那么，请问一共有多少种不同的路径。
乍一看，好像可以遍历，依次向下或者向右找 (i + 1, j) 或者 (i, j + 1)， 直至 (N, M)
比如下面这个简单版本：
WX20191221-184951.png
有六种路径：
WX20191221-190154@2x.png
整理一下，相当于：
从(0, 0)开始，因为我们只能向下或者向右，所以我们先选择一条路去走，比如向右，这时候我们就走到了(1, 0)
WX20191221-190659@2x.png
打叉的部分不代表不能走，只是代表当前流程下，我们只能选其一，也就是右
然后我们在(1, 0)，继续走，可以向右或者向下，我们依然选择向右，这时候我们走到了(2, 0)
WX20191221-190841@2x.png
然后再往下走，直至走到(N, M)，
然后(1, 0)，选择另外一条路，因为这仅仅是个 3*3 的表格，所以我们只能向下
WX20191221-191051@2x.png
然后继续选择一个方向走直至(M, N)。
如此往复。
这样的话，其实可以转换成一个递归，也就是从(i, j) => (i + 1, j) | (i, j + 1)，然后从(i + 1, j) => (x, y) 这样的一个递归方程式，不过这样性能是很差的，而且表格一旦规模变大，就会爆栈。
那么，我们如何有效的解决这个问题呢？
动态规划
ok，我们再次观察这个表格，我们其实会发现一个规律，就是套娃。
没错，表格把表格套娃了。
WX20191221-192112@2x.png
这样一来，参考俄罗斯套娃，每个娃娃其实都是一样的，也就是本质一样，只不过体量逐渐变大，并且最小的那个娃娃不能继续套娃，也就是最小的那个娃娃就是起点。
如此一来，我们姑且可以用俄罗斯套娃来翻译一下这套题。
问：N个俄罗斯套娃合体后的总重量是多少？
答：由于最小的一个套娃无法继续套，并且可以得知这个套娃的重量，所以：
有二个套娃的时候，重量是最小的加上第二个
有三个套娃的时候，重量是两个套娃的重量的加上第三个
有四个套娃的时候，重量是三个套娃的重量的加上第四个
.
.
.
.
有N个套娃的时候，重量是(N - 1)个套娃的重量加上第N个
由此，我们可以得到一个式子：
dp(i) = dp(i - 1) + dp(i)
有没有感觉和表格题有些许类似？
我们可以任意 N * M 的右下角作为结束点，每一个都是一个套娃的角色，可能在当前环中是大套娃，但是到了下一环就成了小套娃，所以这个表格其实就是升级版的套娃。
WX20191221-193148@2x.png
聪明的你，是不是发现了这个升级点在哪？没错，就是一次从(1, 1)开始，每次都是套两个娃，也就是理当前结束点最近的两个娃 => (1, 0) 和 (0, 1)
这样一来我们的公式自然而然就出来了，就是：
dp(N, M) = dp(N - 1, M) + dp(N, M - 1)
七点就是当N或者M为0的时候，也就是这个表格为一条直线，所以总路径都是1
这样我们的代码也就很容易写出来了，并且效率提升，不会有爆栈的问题，还做了之前的缓存。
function taowa(table) {
for (let yLen = table.length, y = yLen - 1; y >= 0; y--) {
for (
let xLen = table[0].length, x = xLen - 1;
x >= 0;
x--
) {
if (x == xLen - 1 || y == yLen - 1) {
table[y][x] = 1;
} else {
table[y][x] = table[y + 1][x] + table[y][x + 1];
}
}
}
return table[y][x];
}
举个例子： 4 * 5的表格有多少种路径？
WX20191221-194713@2x.png
答： 35种
后续看到这，聪明的你会觉得，这个也太简单了吧，没错，算法就是这样。
难者不会，会者不难。
然后如果稍稍加点改造，可能又会花很长时间去这种类似套娃的规律，因为每种套娃的方式都不一样。
比如，还是这样表格，不求不同所有路径数量，将每个cell换成一个数字，求左上角到右下角的经过路径的路径内数字相加的最小值。也就是求最优解。
如下图：
WX20191221-195124.png
这道题的代码是什么呢？初学动态规划的朋友们可以一起讨论讨论
最后，简单总结下。
问题总是变幻莫测，只要你能找到其中的规律，一定能找到对应的解法。
对于动态规划这类问题，有几个特点：
- 有重复子问题(套娃)
- 单项(左上 => 右下)
- 分析作图后，结果类似二叉树
网友评论