动态规划

1、定义数组元素的含义

dp[i][j]表示到达dp[i][j]的路径数量

2、找出数组元素间的关系式

有两种⽅式到达 ⼀种是从 (i-1, j) 这个位置⾛⼀步到达
⼀种是从(i, j - 1) 这个位置⾛⼀步到达
所以有 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

3、初始值

dp[0] [0….n-1] = 1; // 相当于最上⾯⼀⾏，只能⼀直往左⾛
dp[0…m-1] [0] = 1; // 相当于最左⾯⼀列，只能⼀直往下⾛

优化

空间复杂度：O（m * n）
优化后，空间复杂度：O（n）
递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]。

从表中可以看到：

• 当你要填充第三，第四....第 n ⾏的时候，第⼀⾏的值永远不会⽤到，只有填充第⼆⾏的值时会⽤到。
• 因此，只需要⽤⼀个⼀维的 dp[] 来保存⼀⾏的历史记录就可以了
• 此时，推导公式为：dp[i] = dp[i-1] + dp[i]。
  比如求（3，2）这个坐标的元素时，是用（3，0）+（2，2），更新下一行的时候，是从左向右开始更新的，也就是相当于dp[i][j] = dp[i-1][j] + dp[i][j-1]。