题目链接

路径问题

题目描述

image.png

实现代码

动态规划实现代码： 将二维的平面通过一维的方式进行记录，flutter展开

  1. class Solution {
  2.     int mod = (int)1e9+7;
  3.     int m, n, N;
  4.     public int findPaths(int _m, int _n, int _N, int _i, int _j) {
  5.         m = _m; n = _n; N = _N;
  7.         // f[i][j] 代表从 idx 为 i 的位置出发，移动步数不超过 j 的路径数量
  8.         int[][] f = new int[m * n][N + 1];
  10.         // 初始化边缘格子的路径数量
  11.         for (int i = 0; i < m; i++) {
  12.             for (int j = 0; j < n; j++) {
  13.                 if (i == 0) add(i, j, f);
  14.                 if (i == m - 1) add(i, j, f);
  15.                 if (j == 0) add(i, j, f);
  16.                 if (j == n - 1) add(i, j, f);
  17.             }
  18.         }
  20.         // 定义可移动的四个方向
  21.         int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
  23.         // 从小到大枚举「可移动步数」
  24.         for (int step = 1; step <= N; step++) {
  25.             // 枚举所有的「位置」
  26.             for (int k = 0; k < m * n; k++) {
  27.                 int x = parseIdx(k)[0], y = parseIdx(k)[1];
  28.                 for (int[] d : dirs) {
  29.                     int nx = x + d[0], ny = y + d[1];
  30.                     // 如果位置有「相邻格子」，则「相邻格子」参与状态转移
  31.                     if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
  32.                         f[k][step] += f[getIndex(nx, ny)][step - 1];
  33.                         f[k][step] %= mod;
  34.                     }
  35.                 }
  36.             }
  37.         }
  39.         // 最终结果为从起始点触发，最大移动步数不超 N 的路径数量
  40.         return f[getIndex(_i, _j)][N];
  41.     }
  43.     // 为每个「边缘」格子，添加一条路径
  44.     void add(int x, int y, int[][] f) {
  45.         int idx = getIndex(x, y);
  46.         for (int step = 1; step <= N; step++) {
  47.             f[idx][step]++;
  48.         }
  49.     }
  51.     // 将 (x, y) 转换为 index
  52.     int getIndex(int x, int y) {
  53.         return x * n + y;
  54.     }
  56.     // 将 index 解析回 (x, y)
  57.     int[] parseIdx(int idx) {
  58.         return new int[]{idx / n, idx % n};
  59.     }
  60. }