动态规划学习--- 矩阵查找唯一路径

题目描述

leetcode地址
一个机器人从m x n的矩阵左上角出发，到达矩阵的右下角，它每次只能前进一格，且只能向右走或者向下走，问：它有多少种方式走到终点？

/**
 * @param {number} m 矩阵的行数
 * @param {number} n 矩阵的列数
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // Your code.
};

题目分析

题目说机器人只能向下走，或者向右走，那么当机器人走到最后一行时，它只有一种前进方式，当机器人走到最后一列时，它同样只有一种前进方式，如下图：

image.png

现在我们按上面的思路，画个表格，表格中的值表示前进的方式，那么我们可以得到：

image.png

再考虑一下当机器人位于其它位置时，它的前进方式有且仅有两种：

image.png

那么我如何知道一个随机位置前进的方式呢？再尝试画几个位置：

image.png

如图的(a)，记(a)位置的坐标是(i, j)，那么反过来看，如果是从终点向(a)靠近，有几条路线呢？很明显从起点出发只能向下或向右，那么从终点出发就只能向上或向左，只有2条路线到达(a)，满足公式(i, j) = (i+1, j) + (i, j+1)。

再如图中的(b)，终点向(b)靠近，有几条路线呢？

image.png

一条经过(a)，一条不经过(a)，经过(a)的路线有2条，记(b)的坐标是(i, j)，则满足公式：(i, j) = (i+1, j) + (i, j+1) = (ai, aj) + (i, j+1) = 3

我们可以将状态一直向前推进，直到出发点。最后，出发点上的数值就是路线的总数。

SHOW ME THE CODE

/**
 * @param {number} m 矩阵的行数
 * @param {number} n 矩阵的列数
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = []
    // 初始化
    for(let i = 0; i < m; i++) {
      dp[i] = []
    }
    // 初始值
    for(let i = 0; i < m; i++) {
      dp[i][n-1] = 1;
    }
    for(let i = 0; i < n; i++) {
      dp[m-1][i] = 1;
    }
    // 状态转移
    for(let i = m-1; i >= 0; i--) {
        for(let j = n-1; j >= 0; j--) {
            dp[i][j] = dp[i+1][j] + dp[i][j+1]
        }
    }
    return dp[0][0]
};

复杂度分析

时间复杂度：O(m*n)

空间复杂度：O(m*n)

扩展练习

leetcode: 查找最小路径和