`

Leetcode - Unique Paths

 
阅读更多

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?

 

public class Solution {
    // dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    // C(m + n, m)
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0)
            return 0;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                else if (i > 0)
                    dp[i][j] = dp[i - 1][j];
                else if (j > 0)
                    dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

 

分享到:
评论

相关推荐

    pcw0118#ZXBlog#LeetCode-62.Unique Paths(不同的路径数量)(简单dp)1

    1、记忆化 2、二维dp 3、滚动优化

    扩展矩阵leetcode-Leetcode:LeetcodeAnswer-Java

    扩展矩阵leetcode ...uniquePaths 63.不同路径II uniquePathsWithObstacles 139.单词拆分 wordBreak 279.完全平方数 numSquares 排序 56.合并区间 merge 75.颜色分类 sortColors 179.最大数 largestNumber 324.摆

    leetcode1477-coding-for-fun:编码乐趣

    62.unique-paths.cpp [TODO] 5. 最长回文子串.cpp 第 3 天: [TODO] 96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 ...

    leetcode分类-LeetCode:力码

    leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 python,部分有解释 Java,部分有解释 Java Associated Documents and Resources Peter norvig神牛Python代码写的很飘逸,果然是有LISP...

    leetcode答案-leetcode:leetcode

    leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。 我数学太差,没找到答案,直接上了动态规划。 Unique Paths II ...

    leetcode棋盘-Algorithms:通用算法实现

    unique_paths.py(类似于 chess_board.c!)+ unique_paths2.py chess_board.c 效率测试 bin_search.py 素数.py 零知识.py Leetcode:现在很多小方案都是leetcode,我主要是为了好玩。 著名算法:Knuth-Morris-Pratt...

    leetcode530-Leetcode:新的开始

    leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    leetcode叫数-Leetcode_JS:leetcode编程题,javascript版本

    Unique Paths 这道题是一道动态规划的题,还算简单。状态转移方程为: path[i][j] = path[i-1][j] + path[i][j-1]; i和j表示的是i*j的网格从左上角到右下角的路径数量。 并且初始的时候path[i][j]都为1。 为方便起见...

    leetcode正方体堆叠-TakeUforward-SDE_180:TakeUforward-SDE_180

    leetcode正方体收藏TakeUforward-...Unique Paths Reverse Pairs (Leetcode) 从 GFG 中通过拼图(自行搜索) Day4: (Hashing) 2 Sum 问题 4 Sum 问题 Longest Consecutive Sequence Longest Subarray with 0 sum 给定

    lrucacheleetcode-LeetcodeSolution:Leetcode刷题的分类和答案记录

    63.Unique Paths II 64.最小路径和 70.爬楼梯 72.编辑距离 122. 买卖股票的最佳时机 II 152.最大积子阵列 198.强盗 322.硬币变化 贪心算法 45.跳跃游戏II 55.跳跃游戏 哈希 1.二和 3.最长不重复字符的子串 49.组字谜...

    leetcode算法题主函数如何写-visual-your-algo:网站暂停升级中

    uniquePaths = function(m, n) { let dp = new Array(m).fill(0).map(() =&gt; new Array(n)); // dp[r][c] represents the number of possible paths from row = 0, col = 0 to row = r, col = c for (let row = 0; ...

    cpp-算法精粹

    Unique Paths II N-Queens N-Queens II Restore IP Addresses Combination Sum Combination Sum II Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump...

Global site tag (gtag.js) - Google Analytics