【Leetcode】62. Unique Paths

每次可以向左或者向下移动一位，求从左上角到右下角最多有多少种走法

方法1

经典DP法，每一格可以由其左边和上面的格子到大，所以我们很容易写出递推方程
dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意边界条件，第一行和第一列的初始值都应该是1，因为遍历是从左往右从下往上并且python 中数组的[-1]位置表示数组的末尾，所以第一行和第一列越界的元素正好为0

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0]* m for i in range(n)]
        
        for i in range(n):
            for j in range(m):
                if i + j == 0:
                    dp[i][j] =1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]     

方法2 递归

代码简单但是time上不够优化的写法，包含着大量的重复计算

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        #mlie  n hang
        if m == 1 or n == 1:
            return 1
        else:
            return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)

优化内存空间

class Solution:
    from functools import lru_cache
    @lru_cache(None)
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # mlie  n hang
        if m == 1 or n == 1:
            return 1
        else:
            return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

但leetcode不支持导入该包
再改进，用dict存储已经计算过的key，使用的时候直接取出即可，避免再次计算

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        self.dict = {}
        return self.helper(m, n)
 
    def helper(self,m, n): 
        if m == 1 or n == 1:
            return 1
        else:
            key = str(m) + "-" + str(n)
            if  key not in self.dict:
                self.dict[key] = self.helper(m - 1, n) + self.helper(m, n - 1)
            return self.dict[key]