企业官网建设流程全解析

题目链接：62. 不同路径

题目解析

动态规划（Dynamic programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费不必要的时间。

通常的解决步骤有五步：

1. 确定状态表示/dp表的含义
2. 确定状态转移方程/递推公式
3. 初始化
4. 确定填表顺序
5. 确定返回值

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例1：

m = 3, n = 7

输出：28

示例2：m = 3, n = 2

如图所示：

输出：3

算法原理

确定状态表示

状态表示/dp表含义可以从题目要求找出，也可以从重复子问题中找出。

通常可以确定以 i 位置为起始或者以 i 位置为结尾。

本题采用后者，因此状态表示：dp[i][j] 表示机器人走到 [i, j] 位置时的不同路径数。

确定状态转移方程

我们随机取一个情况，从最近的一步来划分问题思考：

1. 取示例2的结束位置Finish为例，到达这个位置时的不同路径数怎么算？
2. 根据题目所说，机器人只能往下或者往右走，因此到达Finish这个位置有两种情况：1. 从它的上方往下走，此时的不同路径数等于其上方位置对应的不同路径数；2. 从它的左方往右走，此时的不同路径数等于其左方位置对应的不同路径数。
3. 综合两种情况，到结束位置时的不同路径数dp[i][j] = dp[i][j-1] + dp[i-1][j]，这就是状态转移方程。

初始化

网格的左边界和上边界需要进行初始化，否则在填表时会越界，例如m=1, n=4（灰色部分表示填表过程中需要访问但越界的位置，称为虚拟节点），其中有红点的位置就是需要初始化的位置：

但是这么多位置需要初始化，也太麻烦了，我们不妨分析一下：只有[-1, 0]这个位置才是需要初始化为1的（其他越界位置都为0）。为什么？位置[0, 0]需要往上访问该位置；而其它位置都需要[0, 0]，所以当[-1, 0]为1，[0, 0]也为1，这样一来，[0, 1]、[0, 2]、[0, 3]就都是1（左1上0），[1, 0]也是1（左0上1）。

基于此，我们的dp表大小应为(m+1)×(n+1)。

确定填表顺序

按照从上往下、从左往右的顺序访问网格，填 dp表（二维数组）。

确定返回值

我们需要返回到达 “Finish” 位置时的不同路径数，因此返回值为dp[m][n]。

代码实现

普通动态规划

classSolution{publicintuniquePaths(intm,intn){// 创建dp表(包含用于初始化的虚拟节点)int[][]dp=newint[m+1][n+1];// 初始化dp[0][1]=1;// 从上往下、从左往右填表for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){dp[i][j]=dp[i][j-1]+dp[i-1][j];}}// 返回结果,到达右下角的路径数dp[m][n]returndp[m][n];}}

空间优化版本

由于dp[i][j]只依赖dp[i][j-1]和dp[i-1][j]这两个值，我们可以不创建整个 dp 二维数组，只保留一行，用一维数组dp[j]来滚动覆盖。

初始的dp[j]数组表示第0行，将dp[1]（原二维数组dp[0][1]）初始化为1之后：dp = {0, 1, 0, 0}。

填表时：

1. 填第一行第一个，原本是dp[1][1] = dp[0][1](上) + dp[1][0](左)，现在改为dp[1] = dp[1] + dp[0]，其中第一个dp[1]代表dp[1][1]，第二个dp[1]代表dp[0][1]（上方格子），dp[0]代表dp[1][0]（左方格子）。
2. 接下来填第一行第二个，dp[2] = dp[2] + dp[1]，这时候dp[2]就由之前的dp[0][2]被更新成dp[1][2]了。
3. 第一行的其他列以此类推，逐个更新为本行的值

此时状态转移方程改为：dp[j] = dp[j] + dp[j-1]。填表顺序依旧是从上往下、从左往右。返回值则是更新后第m行第n列的值dp[n]。

classSolution{publicintuniquePaths(intm,intn){// 一维数组：dp[j] 在更新前代表"上一行"的 dp[i-1][j]// 更新后代表"当前行"的 dp[i][j]int[]dp=newint[n+1];// 对应原来的 dp[0][1] = 1（第0行第1列为1，充当"起点上方"的虚拟值）dp[1]=1;// 从上往下、从左往右滚动for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){dp[j]=dp[j]+dp[j-1];}}returndp[n];// 循环结束时 dp[n] 就是 dp[m][n]}}