LeetCode - Unique Paths
2025-02-02 23:58:02 来源: 阅读:
题目：
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 3 x 7 grid. How many possible unique paths are there?
思路：
动态规划，到达某一点的路线数是其上和左的节点的路线数之和。我们也可以用C(M+N-2, M-1)来计算，即C(8, 2) = 28.
package dp; public class UniquePaths { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; dp[0][0] = 1; 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]; } public static void main(String[] args) { // TODO Auto-generated method stub UniquePaths u = new UniquePaths(); System.out.println(u.uniquePaths(3, 7)); } }