Unique Paths (M)
題目
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?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
題意
在矩形中找到一條路徑，起點為左上頂點，終點為右下頂點，路徑中只能向右或向下走，要求統計不同路徑的個數，
思路
組合數：因為每次只能向右或向下走，所以符合條件的路徑的長度必然是 m+n-2，其中有 m-1 個點是向右走，n-1 個點是向下走，問題就轉化為了在 m+n-2 個點中找出 m-1 個點(或找出 n-1 個點，都一樣)，求\(C_{m+n-2}^{m-1}\)的值，
組合數求值可以用公式：\(C_n^m=\frac{n!}{m!(n-m)!}\)，也可以用遞推公式計算：\(C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\)，
動態規劃：dp[i][j]記錄可以到達位置(i, j)的路徑的數目，因為(i, j)只可能從(i, j-1)向右走到達，或者從(i-1, j)向下走到達，所以有 \(dp[i][j]=dp[i][j-1]+dp[i-1][j]\)，
注意到dp[i][j]只與左邊和上邊的dp有關，且我們的目標只是為了得到最后一行最后一列的dp，所以可以用滾動陣列對上述程序進行空間優化，無需使用二維陣列，
代碼實作
Java
組合數
public int uniquePaths(int m, int n) {
return calculate(m + n - 2, m - 1);
}
private int calculate(int n, int m) {
double ans = 1.0;
while (m >= 1) {
ans *= 1.0 * n-- / m--;
}
return (int) Math.round(ans);
}
動態規劃
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[n][m];
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i != 0 || j != 0) {
dp[i][j] = findDP(dp, i - 1, j) + findDP(dp, i, j - 1);
}
}
}
return dp[n - 1][m - 1];
}
private int findDP(int[][] dp, int i, int j) {
if (i < 0 || j < 0) {
return 0;
}
return dp[i][j];
}
}
滾動陣列優化
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[m];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[j] = dp[j] + (j > 0 ? dp[j - 1] : 0);
}
}
return dp[m - 1];
}
}
JavaScript
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function (m, n) {
let scroll = new Array(m).fill(1)
for (let i = 1; i < n; i++) {
for (let j = 0; j < m; j++) {
scroll[j] = j === 0 ? scroll[j] : scroll[j] + scroll[j - 1]
}
}
return scroll[m - 1]
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21315.html
標籤：其他