0%

动态规划：计算路径数目(有限拐点)

发表于 更新于 分类于 阅读次数：
本文字数： 2.2k 阅读时长 ≈ 4 分钟

一道有趣的动态规划题目

问题描述

给定一个 m x n 大小的矩阵，计算从左上角到右下角的路径数量（只允许向下或者向右移动），要求路径所经历的拐点数目不大于 k。

什么是拐点？如果我们本来沿着行移动，但是现在沿着列移动，则认为路径经过了一个拐点；或者本来沿着列移动，现在沿着行移动。拐点可能发生时有两种可能的情况：

在点 (i, j)：

  • 向右转： (i-1, j) -> (i, j) -> (i, j + 1)
  • 向下转： (i, j-1) -> (i, j) -> (i + 1, j)

对于下图：

1
2
3
4
5
输入：m = 3，n = 3，k = 2
输出：4

输入：m = 3，n = 3，k = 1
输出：2

求解分析

这是一道典型的动态规划题目，可以列出转移方程的形式。

首先定义计算路径的函数：

  • countPaths(i，j，k)：从 (0, 0) 到达 (i, j) 的路径的数量
  • countPathsDir(i，j，k，0)：沿着行方向到达 (i, j) 的路径数量。
  • countPathsDir(i，j，k，1)：沿着列方向到达 (i, j) 的路径数量。

countPathsDir 中的第四个参数表示方向。因此：countPaths(i，j，k) = countPathsDir(i，j，k，0) + countPathsDir(i，j，k，1)

countPathsDir 的值可以递归地定义为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 如果当前方向是沿着行
if (d == 0)
{
  // 计算两种情况的路径
  // 1）我们通过前一行到达这里。
  // 2）我们通过前一列到达此处，因此数量为将 k 减少 1。
  
  countPathsDir(i, j, k, d) = countPathsUtil(i, j-1, k, d) + countPathsUtil(i-1, j, k-1, ！d);
}

// 如果当前方向是沿列
else
{
  //与上面类似

  countPathsDir(i, j, k, d) = countPathsUtil(i-1, j, k, d) + countPathsUtil(i, j-1, k-1，！d);
}

编程实现

我们可以使用动态编程在多项式时间中解决这个问题。想法是使用 4 维表 dp[m][n][k][d] 其中 m 是行数，n 是列数，k 是剩余的拐点数目，d 是方向。

下面是基于动态编程的 C++ 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define MAX 100

int dp[MAX][MAX][MAX][2];

// Returns count of paths to reach (i, j) from (0, 0) using at-most k turns. 
// d is current direction d = 0 indicates along row, d = 1 indicates along column. 

int countPathUtil(int i, int j, int k, int d)
{
  if (i < 0 || j < 0)
  {
    return 0;
  }

  // 动态规划的边界条件：1 x 1 矩阵的情况
  if (i == 0 && j == 0)
  {
    return 1;
  }

  // 动态规划的边界条件：拐点数目已经达到极限
  if (k == 0)
  {
    // 只有当前方向是along row，并且重点行坐标 i == 0 才可能到达。
    // 否则，必然还需要最少一个拐点。
    if (d == 0 && i == 0)
    {
      return 1;
    }
    // 同理
    if (d == 1 && i == 1)
    {
      return 1;
    }

    return 0;
  }
  
  // 如果这个问题已经被求解了，直接返回结果
  if (dp[i][j][k][d] != -1)
  {
    return dp[i][j][k][d];
  }

  // 递归求解
  if (d == 0)
  {
    return dp[i][j][k][d] = countPathUtil(i, j-1, k, d) + countPathUtil(i-1, j, k-1, 1-d);
  }
  else
  {
    return dp[i][j][k][d] = countPathUtil(i-1, j, k, d) + countPathUtil(i, j-1, k-1, 1-d);
  }
}

int countPath(int i, int j, int k)
{
  if (i == 0 && j == 0)
  {
    return 1;
  }
  memset(dp, -1, sizeof(dp));

  // 沿着行方向移动和沿着列方向移动，到达 (i, j) 的两种方式
  return countPathUtil(i-1, j, k, 1) + countPathUtil(i, j-1, k, 0);
}

int main()
{
  int m = 3, n = 3, k = 2;
  
  cout << "Number of paths is " << countPath(m-1, n-1, k) << endl;
  
  return 0;
}