14.4 矩阵路径问题

矩阵路径问题通常输入一个矩阵, 计算路径数目或者最短路径.

和双序列类似, 状态转移函数为$f(i,j)$.

迭代的计算过程需要用到二维数组, 可以优化成一维数组.

14.4.1 问题98: 路径数目

LCR 098. 不同路径

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

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

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

示例 1：

img

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

14.4.1.1 分析&题解

每走一步都有两个选择(下或右), 到达目的需要多步, 若列举出所有路径使用回溯法.

路径数目使用动态规划.

状态转移方程

$f(i,j)$表示(0,0)到(i,j)的路径数, 格子大小m*n, $f(m-1,n-1)$就是问题的解.

对于坐标(i,j), $f(i,j)$表示走到此处的路径数, 可以从(i-1,j)向下一步,或从(i,j-1)向右一步.

所以 $f(i,j)=f(i-1,j)+f(i,j-1)$.

初始值(最小问题解):

• $f(i,0)$: 最左边, 不可能从右边走过来, 路径数为 1
• $f(0,j)$: 最上边, 不可能从上边走过来, 路径数为 1

迭代+二维数组

每次只用两行, 只需两行二维数组

func uniquePaths(m int, n int) int {
    // 缓存
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // 初始值, 最小问题解
    dp[1][0] = 1
    for i := 0; i < n; i++ {
        dp[0][i] = 1
    }
    
    // 计算
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i%2][j] = dp[(i-1)%2][j] + dp[i%2][j-1]
        }
    }
    
    return dp[(m-1)%2][n-1]
}

迭代+一行二维数组

计算时只需要上一个和左边一个的数据, 可优化为一维数组

func uniquePaths(m int, n int) int {
    // 缓存
    dp := make([]int, n)
    // 初始值
    for i := range dp {
        dp[i] = 1
    }

    // 计算
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] = dp[j-1] + dp[j]
        }
    }

    return dp[n-1]
}

14.4.2 问题99: 最小路径和

LCR 099. 最小路径和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**一个机器人每次只能向下或者向右移动一步。

示例 1：

img

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

14.4.2.1 分析&题解

每有两个选择, 需要走多步才能到达终点, 若需要列出所有的路径使用回溯法.

找出最小路径使用动态规划.

状态转移方程

假设到达坐标(i,j)处的最小路径和为$f(i,j)$

• 从(i-1,j)过来, $f(i,j)=f(i-1,j)+grid[i][j]$
• 从(i,j-1)过来, $f(i,j)=f(i,j-1)+grid[i][j]$

那么状态转移方程为: $f(i,j)=min(f(i-1,j),f(i,j-1))$

初始值(最小问题解):

• $f(0,j)$: 只能右移到达, $f(0,j)=\sum_{k=0}^jgrid[0][k]$
• $f(i,0)$: 只能下移到达, $f(i,0)=\sum_{k}^igrid[k][0]$

迭代+两行二维数组

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    // 缓存 
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    // 初始值(最小问题解)
    sum := 0
    for i := 0; i < n; i++ {
        sum += grid[0][i]
        dp[0][i] = sum
    }

    // 计算
    for i := 1; i < m; i++ {
        // 新的一行
        dp[i%2][0] = dp[(i-1)%2][0] + grid[i][0]
        for j := 1; j < n; j++ {
            dp[i%2][j] = min(dp[(i-1)%2][j], dp[i%2][j-1]) + grid[i][j]
        }

    }

    return dp[(m-1)%2][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

迭代+一维数组

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    // 缓存
    dp := make([]int, n)
    // 初始值, 最小问题解
    dp[0] = grid[0][0]
    for i := 1; i < n; i++ {
        dp[i] = dp[i-1] + grid[0][i] 
    }

    // 计算
    for i := 1; i < m; i++ {
        // 新的一行
        dp[0] += grid[i][0]
        for j := 1; j < n; j++ {
            dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
        }
    }

    return dp[n-1]
}   

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

14.4.3 三角形中最小路径和

LCR 100. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

提示：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

14.4.3.1 分析&题解

每步有两个选择(下方或下方相邻的节点), 解决问题需要多步, 若列出所有路径可以使用回溯法.

找出最小路径使用动态规划.

状态转移方程

三角形实际上为矩阵[0,n-1][0,n-1]的下半部分,即满足$i\ge j$.

对于当前坐标(i,j), $f(i,j)$表示最小路径和, 那么$f(n-1, j)$的最小值为问题的解.

对于$f(i,j)$:

• $j=0$时, 只能从正上方位置向下, $f(i,j)=f(i-1,j)+tri[i][j]$
• $i=j$时, 只能从上方位置到下方相邻位置, $f(i,j)=f(i-1,j-1)+tri[i][j]$
• $i>j$时, 有两个选择, $f(i,j)=min(f(i-1,j),f(i-1,j-1))+tri[i][j]$

初始值(最小问题解):

• $f(0,0)$: tri[0][0]

迭代+一维数组

每次计算只用到上一行的数字, 使用一维数组即可.

使用dp[j]保存上一行的数据$f(i-1, j)$, 由于$f(i-1,j-1)$下次计算还需要, 不能用$f(i-,j)$直接替换, 使用prev暂存.

func minimumTotal(triangle [][]int) int {
    // 三角形的底边长度
    n := len(triangle[len(triangle)-1])

    // 缓存
    dp := make([]int, n)

    // 计算
    for i := 0; i < n; i++ {
        // 缓存 f(i-1,j-1)
        prev := dp[0]
        for j := 0; j <= i; j++ {
            cur := 0 // 缓存计算结果
            if j == 0 {
                cur = dp[j] + triangle[i][j]
            } else if  i == j {
                cur = prev + triangle[i][j]
            } else if  i > j { 
                cur = min(dp[j], prev) + triangle[i][j]
            }

            prev = dp[j] // 缓存之前的结果 
            dp[j] = cur  // 保存计算结果
        }
    }

    res := dp[0]
    for _, v := range dp {
        res = min(res, v)
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Reference

1. 剑指Offer（专项突破版）