首页 > 其他 > 详细

LeetCode Unique Paths

时间:2014-03-16 05:05:27      阅读:438      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
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];
    }
};
bubuko.com,布布扣

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-1), 向右移动得到(i, j)
  • (i-1, j), 向下移动得到(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

LeetCode Unique Paths

原文:http://www.cnblogs.com/lailailai/p/3600928.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!