【LeetCode刷题】70 爬楼梯 || 62 不同路径

70、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。

示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

#递归
class Solution1(object):
    def climbStairs(self, n):
        if n==1:
            return 1
        if n==2:
            return 2
        if n>2:
            return self.climbStairs(n-2)+self.climbStairs(n-1)

solution = Solution1()
print(solution.climbStairs(8))

#动态规划
class Solution2:
    def climbstairs(self,n):
        if n <=2:
            return n
        a = 0
        a1 = 1
        a2 = 2
        if n>2:
            for i in range(2,n):
                a = a1 + a2
                a1,a2 = a2,a
            return a

solution = Solution2()
print(solution.climbstairs(8))

62、不同路径

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，给一个m x n的网格，有多少可能的路径？

总结：利用动态规划解决，第一行第一列的所有方式只有1种，到达其他位置的方式是这个位置上面 + 这个位置左边

class Solution:
    def uniquePaths(self, m, n):
         square = [[1 for i in range(n)] for i in range(m)]
         for i in range(m):
             for j in range(n):
                 if i==0 or j==0:
                     square[i][j] = 1

                 else:
                     square[i][j] = square[i-1][j]+square[i][j-1]

         return square[m-1][n-1]

class Solution2(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        memo = [[0] * n for _ in range(m)]
        return self.dfs(m - 1, n - 1, memo)

    def dfs(self, m, n, memo):
        if m == 0 or n == 0:
            return 1
        # if memo[m][n]:
        #     return memo[m][n]
        up = self.dfs(m - 1, n, memo)
        left = self.dfs(m, n - 1, memo)
        memo[m][n] = up + left
        print(memo[m][n])
        return memo[m][n]


#有阻挡物
# class Solution1(object):
#     def uniquePathsWithObstacles(self, obstacleGrid):
#         """
#         :type obstacleGrid: List[List[int]]
#         :rtype: int
#         """
#         m, n = len(obstacleGrid), len(obstacleGrid[0])
#         dp = [[0] * (n + 1) for _ in range(m + 1)]
#         for i in range(1, m + 1):
#             for j in range(1, n + 1):
#                 if obstacleGrid[i - 1][j - 1] == 1:
#                     dp[i][j] = 0
#                 else:
#                     if i == j == 1:
#                         dp[i][j] = 1
#                     else:
#                         dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
#         return dp[m][n]


m=7
n=6
a=[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
solution = Solution()
solution2 = Solution2()
print(solution.uniquePaths(m,n))
print(solution2.uniquePaths(m,n))