class Solution { public: int uniquePaths(int m, int n) { int (*dp)[101] = new int[101][101]; for (int i=0;i<101;i++) dp[0][i] = 0; for (int i=0;i<101;i++) dp[i][0] = 0; dp[0][1] = 1; for (int i=1; i<=m; i++) { for (int j=1; j<=n; j++) { // to reach (i,j), we can move from // 1. (i, j-1), move right 1 block // 2. (i-1, j), move down 1 block dp[i][j] = dp[i][j-1] + dp[i-1][j]; } } return dp[m][n]; } };
1. 存在直接的计算公式组合数C(m+n-2, n-1),在m+n-2步移动中选取n-1或m-1种为相应维度上的移动方式(向右或向下)
2. 采用动态规划,要是学高级数据结构时老师能先举个这样简单的例子就好了。
dp[i][j]代表到达坐标(i, j)(i、j从1开始编号)的路径种数,因为题目规定只能向右或者向下移动,所以在dp[i][j]的上一步,其坐标肯定是
那么到达(i, j)的路径总数就是这两种情况的和即dp[i][j] = dp[i-1][j] + dp[i][j-1]
不过题目虽然说 "m and n will be at most 100.", 但是其测试数据显然没有达到这个范围,因为返回的是int类型,而这个问题的解数目会迅速增加,(100, 100)时数量级别是10的58次方,或许答案可以改为mod一个数后的取值。
LeetCode Unique Paths,布布扣,bubuko.com
原文:http://www.cnblogs.com/lailailai/p/3600928.html