首页 > 代码库 > [leetcode]Unique Paths @ Python
[leetcode]Unique Paths @ Python
原题地址:https://oj.leetcode.com/problems/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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
解题思路:这道题和climbing stairs很像,可以用动态规划解决。状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]。
代码:
class Solution: # @return an integer def uniquePaths(self, m, n): if m == 1 and n == 1: list = [[1]] elif m == 1 and n > 1: list = [[1 for i in range(n)]] elif m > 1 and n == 1: list = [[1] for i in range(m)] else: list = [[0 for i in range(n)] for i in range(m)] for i in range(0, n): list[0][i] = 1 for i in range(0, m): list[i][0] = 1 for i in range(1, m): for j in range(1, n): list[i][j] = list[i-1][j] + list[i][j-1] return list[m-1][n-1]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。