题目链接

不同路径

题目描述

image.png

实现代码

dfs深度优先遍历思想，超时：

  1. class Solution {
  2.     int result = 0;
  4.     public int uniquePaths(int m, int n) {
  5.         dfs(1, 1, m, n);
  6.         return result;
  7.     }
  9.     public void dfs(int i, int j, int m, int n) {
  10.         if(i > m || j > n) {
  11.             return;
  12.         }
  13.         if(i == m && j == n) {
  14.             result++;
  15.             return;
  16.         }
  17.         dfs(i+1, j, m, n);
  18.         dfs(i, j+1, m, n);
  19.     }
  20. }

动态规划思想：dp[i][j]记录从(1,1)到位置(i,j)的路径数，状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i][j-1];

初始化条件:

dp[1][j] = 1 j取任何数 dp[i][1] = 1 i取任何数

实现代码：

  1. class Solution {
  3.     public int uniquePaths(int m, int n) {
  5.         int[][] dp = new int[m+1][n+1];
  7.         for(int i=1; i<=m; i++) {
  8.             dp[i][1] = 1;
  9.         }
  10.         for(int j=1; j<=n; j++) {
  11.             dp[1][j] = 1;
  12.         }
  14.         for(int i=2; i<=m; i++) {
  15.             for(int j=2; j<=n; j++) {
  16.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  17.             }
  18.         }
  20.         return dp[m][n];
  21.     }
  22. }

在二维数组的基础上进行降维优化，实现代码如下：

  1. class Solution {
  2.     public static int uniquePaths(int m, int n) {
  4.         int[] dp = new int[n];
  5.         dp[0] = 1;
  6.         for(int i = 0; i < m ; i++){
  7.             for(int j = 1; j < n; j++){
  8.                 dp[j] = dp[j - 1] + dp[j];
  9.             }
  10.         }
  11.         return dp[n - 1];
  12.     }
  13. }