一个机器人在m×n大小的地图的左上角(起点)。
机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。
可以有多少种不同的路径从起点走到终点?
备注:m和n小于等于100,并保证计算结果在int范围内
数据范围:,保证计算结果在32位整型范围内
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
2,1
1
2,2
2
public int uniquePaths (int m, int n) { int[][] dp=new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j==0){ dp[i][j]=1; }else if(i==0){ dp[i][j]=1; }else if(j==0){ dp[i][j]=1; }else{ dp[i][j]=dp[i][j-1]+dp[i-1][j]; } } } return dp[m-1][n-1]; }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here return Combination(m+n-2, m-1); } private static int Combination(int n, int k) { if(k==0||k==n) return 1; else return Combination(n-1, k)+Combination(n-1, k-1); } }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here if(m == 1){ return 1; }else if(n == 1 ){ return 1; } return uniquePaths(m-1, n) + uniquePaths(m, n-1); } }
public int uniquePaths (int m, int n) { // write code here int dp[][] = new int[m][n]; for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 0; i < m; i++) { dp[i][0] = 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]; }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 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]; } }
public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here int[][] dp = new int[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(i == 0 || j == 0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i][j-1] + dp[i-1][j]; } } } return dp[m-1][n-1]; } }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here if (m == 1 || n == 1) return 1; int[][] dp = new int[m][n]; for (int i = 1; i < m; i ++) dp[i][0] = 1; for (int i = 1; i < n; i ++) dp[0][i] = 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]; } }
import java.util.*; public 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 i = 0; i < n; i ++) dp[0][i] = 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]; } }
public int uniquePaths (int m, int n) { // write code here int[][] dp = new int[m][n]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0||j==0){ dp[i][j]=1; }else{ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } return dp[m-1][n-1]; }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here //二维数组 //记录方案 int[][] dp = new int[m][n]; //m = row dp[0][0] = 1; //n = col for(int i = 1;i<n;i++){ dp[0][i] = 1; } for(int i = 1;i<m;i++){ dp[i][0] = 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]; } }
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ int count = 0; public int uniquePaths (int m, int n) { // write code here //使用递归 /* if(m <= 0 || n <= 0) return 0; //follow数学题解 if(m == 1) return 1; if(n == 1) return 1; return uniquePaths(m-1,n) + uniquePaths(m, n-1); */ if(m==1) return 1; if(n==1) return 1; int[][] array = new int[m][n]; for(int i = 0; i<n; i++) { array[0][i] = 1; } for(int i = 0; i<m ; i++) { array[i][0] = 1; } for(int i = 1; i<m; i++) { for(int j = 1; j<n; j++) { array[i][j] = array[i-1][j] + array[i][j-1]; } } return array[m-1][n-1]; } }
动态规划DP:推导出DP方程很重要
import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here // dp方程 int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 经过分析:当i==0时,j为任何值,dp[0][x]=1; // 当j == 0,i 为任何值,dp[i][j]=1; if (i == 0 || j == 0) { dp[i][j] = 1; continue; } // 经分析推到DP方程 dp[i][j] = dp[i][j - 1] + dp[i - 1][j]; } } return dp[m - 1][n - 1]; } }
思路:先明确题目给的条件,只能往右或往下走,因此递推方程为:dp[i][j]=dp[i-1][j]+dp[i][j-1];
当然,最左边和最上边的都为1,毕竟只有一条路径
import java.util.*; public class Solution { public int uniquePaths (int m, int n) { // write code here int[][] dp=new int[m][n]; for(int i=0;i<n;i++){ dp[0][i]=1; } for(int i=0;i<m;i++){ dp[i][0]=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]; } }