题目

image.png

思路

  • 可以理解为斐波那契额类型题目
  • 思路一：暴力递归，想要达到(m,n)位置，只要计算去到(m-1, n)和(m, n - 1)位置可能性之和即可，因此得到了递归条件。什么时候结束呢，很明显当m==1或者n==1时，只有一种选择。
  • 思路二：备忘录递归，使用容器记录已经走过的(m,n)避免重复计算

  • 思路三：动态规划，从递归思路我们知道计算(m,n)位置，要先计算(m-1,n)和(m,n-1)，也就是说，如果已知(m-1,n)和(m,n-1)，就可以计算(m,n)，那么现在已知(1,j)=1和(i,1)=1，i在1~m，j在1~n。遍历整个二维dp数组就可知道各个(i,j)的值 | i\j | 1 | 2 | 3 | | —- | —- | —- | —- | | 1 | 1 | 1 | 1 | | 2 | 1 | 1+1=2 | 2+1=3 | | 3 | 1 | 1+2=3 | 3+3=6 | | 4 | 1 | 1+3=4 | 4+6=10 |

  • 思路四：动态规划优化dp数组，通过上述表格可以发现每次只是用到了上次遍历的一列而已，所以可以将二维数组优化为一维数组，记录上次的值即可

    代码

    1.   //1. 暴力递归，超时
    2.   public int uniquePaths(int m, int n) {
    3.       if (m == 1 || n == 1) return 1;
    4.       return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    5.   }
    7.   //2. 备忘录
    8.   Map<String, Integer> table = new HashMap<>();
    9.   public int uniquePaths(int m, int n) {
    10.       if (m == 1 || n == 1) return 1;
    11.       String key1 = m + "-" + n;
    12.       String key2 = n + "-" + m;
    13.       if (table.containsKey(key1) || table.containsKey(key2)) 
    14.           return table.containsKey(key1) ? table.get(key1) : table.get(key2);
    15.       int count = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    16.       if (!table.containsKey(key1) && !table.containsKey(key2))
    17.           table.put(key1, count);
    18.       return count; 
    19.   }
    21.   //3. 动态规划
    22.   public int uniquePaths(int m, int n) {
    23.       if (m == 1 || n == 1) return 1;
    24.       int[][] dp = new int[m][n];
    25.       for (int i = 1; i < m; i++) {
    26.           for (int j = 1; j < n; j++) {
    27.               if (i - 1 == 0) dp[i - 1][j] = 1;
    28.               if (j - 1 == 0) dp[i][j - 1] = 1;
    29.               dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    30.           }
    31.       }
    32.       return dp[m - 1][n - 1];
    33.   }
    35.   //4. 优化动态规划的dp数组
    36.    public int uniquePaths(int m, int n) {
    37.       if (m == 1 || n == 1) return 1;
    38.       int[] dp = new int[n];
    39.       for (int i = 0; i < n; i++) {
    40.           dp[i] = 1;
    41.       }
    42.       for (int i = 1; i < m; i++) {
    43.           for (int j = 1; j < n; j++) {
    44.               dp[j] += dp[j - 1];
    45.           }
    46.       }
    47.       return dp[n - 1];
    48.    }

    不同路径