武汉百度推广电话_安徽省建设工程信用信息网_凡科网站登录入口_百度浏览器

题目链接：

链接

题目描述：

思路：

设走到$(i,j)$的路径有$dp[i][j]$条，由于只能向右或下走，所以
$$dp[i][j]=dp[i-1][j]+dp[i][j-1]$$

注意在边界上：第一行和第一列，dp值都为1（因为只能向右或下走，所以到达同一行或同一列只有一条路）

可以发现，$(i,j)$位置只和本行和上一行的有关，所以只记一行就行

实现代码：

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0; i < m; i++){dp[i][0] = 1;}for(int j = 0; j < n; j++){dp[0][j] = 1;}for(int i =1 ; i < m ; i++){for(int j = 1; j < n; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

2. 记一行

class Solution {public int uniquePaths(int m, int n) {int[] dp = new int[n];for(int j = 0; j < n; j++){dp[j] = 1;}for(int i =1 ; i < m ; i++){for(int j = 1; j < n; j++){dp[j] = dp[j-1] + dp[j];}}return dp[n-1];}
}