【蓝因子教育】算法设计里面的数学方法
今天要说一个简单但是有意思的算法小题。这题让我深刻体会到
Math is the king.如果懂数学那这题真正可以做到秒出答案，时间复杂度、空间复杂度将被大大优化。
题目很简单:
假设你是一个机器人，要从左上角走到右下角。每次只能走一步，要么往下走，要么往右走。问从左上角走到右下角一共有多少步走法？每次只能走一步
常规解法是基本的动态规划 Dynamic Programming 即 bottom-up approach。
首先来回顾一下解动态规划的 4 个基本步骤。
1 确定状态 States
两个意识：子问题 最后一步
Sub problem / Last state
2 转移方程 Transition function
主要是列出转移方程 f(i) = ... f(i-1)
3 初始条件和边界情况 Initial state / Edge cases
初始条件：不能用方程直接计算得出的
边界条件：在运算过程中需要考虑处理的
4 计算顺序 Order
这一题明显是从小到大
由于小人每次只能走一步，那么可以得出在出发位置从左走到右边任何一个格子都只有一种走法；同理从上走到下都只有一种走法。所以最开始的全都是 1，如下图所示。
DP 推理表格
有了初始位置，再来看转移方程。
在中间的任何一个位置都是其上方格子 + 左边格子的和。具体如上面箭头所示。
初始条件是最开始的全部格子都只有 1 种走法。走完所有的格子就算完毕。
有了这些分析就可以开始写代码，下面是伪代码。
dp = [];dp = new Array(m);for(i, 0 -> n): dp[i] = new Array(n); dp[i][0] = 1;dp[i].fill(1);for(i, 0 -> m): for(j, 0 -> n): dp[i][j] = dp[i-1][j] + dp[i][j-1];dp[m-1][n-1]; // 答案
时间复杂度是 O（M + N），空间复杂度是（M + N）
简单吧，是不是你遇到过最简单的 DP。那还有更简单的办法吗？
有。用数学公式秒出答案。
可以把所有的移动放到一起，然后每次从里面选择一种移动方式。正好可以用到数学的”排列“公式，即 C(n,r)=n!/(r!(n−r)!)
用数学的思路来解题
7 个横向格子有 7-1 个移动；3 个竖向格子有 3-1 个移动。一共就是 8 个移动。每次移动可选择 2 个方向，所以就是在 8 个移动里面选择 2 个移动方向的组合方式。
C(8, 2) = 8! / (2! * 6!) = 28
是不是秒出答案？
走法格子复杂度dp方程发布于：湖南省声明：该文观点仅代表作者本人，搜狐号系信息发布平台，搜狐仅提供信息存储空间服务。