LeetCode -- Unique Paths

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]




實現代碼：

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];
    }
}