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列地图,物体从左上角开始移动,有多少种路径可以到达右下角,
LeetCode Unique Paths
。物体只能向右或下移动。本题是一个典型的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]; }}