LeetCode -- Unique Paths
Unique Paths
题目描述：
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
给定一个m行n列地图，物体从左上角开始移动，有多少种路径可以到达右下角。物体只能向右或下移动。
本题是一个典型的DP问题。
当只有一行（即m=1）时，无论n为几，都只有1种，即dp[1,n] = 1;
当m>1时，dp[m,n]至少等于dp[m-1,n]（即向下走一步） ，如果n>0 dp[m,n]还要加上dp[m,n-1]（即向右走一步）
因此递推公式为：
m=1: dp[m,n] = 1;
m > 1 & n = 0: dp[m-1,n]
m > 1 & n > 0 : dp[m-1,] + dp[m , n-1]
实现代码：
题目描述：
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
给定一个m行n列地图，物体从左上角开始移动，有多少种路径可以到达右下角。物体只能向右或下移动。
本题是一个典型的DP问题。
当只有一行（即m=1）时，无论n为几，都只有1种，即dp[1,n] = 1;
当m>1时，dp[m,n]至少等于dp[m-1,n]（即向下走一步） ，如果n>0 dp[m,n]还要加上dp[m,n-1]（即向右走一步）
因此递推公式为：
m=1: dp[m,n] = 1;
m > 1 & n = 0: dp[m-1,n]
m > 1 & n > 0 : dp[m-1,] + dp[m , n-1]
实现代码：
public class Solution {
public int UniquePaths(int m, int n) {
// m : row
// n : col
if(m < 1){
return 0;
}
if(m == 1){
return 1;
}
var dp = new int[m, n];
// set first [row, i] as 1 , i : [0,n)
for(var i = 0;i < n; i++){
dp[0, i] = 1;
}
for(var i = 1;i < m; i++){
for(var j = 0;j < n; j++){
dp[i, j] = dp[i-1, j];
if(j > 0){
dp[i, j] += dp[i, j-1];
}
}
}
return dp[m-1, n-1];
}
}