12赞
654
当前位置:  开发笔记 > 编程语言 > 正文

LeetCode62.UniquePaths

使用动态规划,思路很清晰使用如下代码,发现超时了这段代码遍历出了所有的路径,而题目只需要路径的数目。使用数组记录,关键在于怎

技术分享图片

使用动态规划,思路很清晰

使用如下代码,发现超时了

int uniquePaths(int m, int n) {
    if (m == 1 || n == 1)
        return 1;
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

这段代码遍历出了所有的路径,而题目只需要路径的数目。

使用数组记录,关键在于怎么确定边界条件

int uniquePaths2(int m, int n) {
    vectorint>> result(m,vector<int>(n,1));
    for (int i = 1; i i) {
        for (int j = 1; j j) {
            result[i][j] = result[i-1][j] + result[i][j - 1];
        }
    }
    return result[m-1][n-1];
}

LeetCode-62. Unique Paths


推荐阅读
author-avatar
sky梦幻
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有