递归的两种情况

递归 和 DP 是不是都可以 自底向上 和 自顶向下 ？？
之前的认知是 DP是自底向上 递归是自顶向下
好像这个认知没啥问题 递归就是要把大问题转成小问题 逐个解决
DP从最小的问题开始递推到最终要解决的大问题

从头计算到后面 （小偷问题）

"""
递归 + memo 
此时 dp(i) 定义为 从第一家偷到第i家
"""
class Solution_rec(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        memo = {-1:0}

        def dp(n):
            if n not in memo:
                if n == 0:
                    res = nums[0]
                elif n == 1:
                    res = max(nums[:2])
                else:
                    res = max(dp(n - 1), nums[n] + dp(n - 2))
                memo[n] = res
            return memo[n]

        return dp(len(nums) - 1)

从尾巴计算到前面 （正则表达式匹配问题）

class Solution_(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        memo = {}

        def dp(i, j):
            if (i, j) not in memo:
                if i == len(s) and j == len(p):  # 00
                    res = True
                elif i != len(s) and j == len(p):  # 10
                    res = False
                else:  # 01 11
                    if j < len(p) - 1 and p[j + 1] == '*':
                        if i < len(s) and p[j] in ['.', s[i]]:
                            res = dp(i, j + 2) or dp(i + 1, j)
                        else:
                            res = dp(i, j + 2)
                    elif i < len(s) and p[j] in ['.', s[i]]:
                        res = dp(i + 1, j + 1)
                    else:
                        res = False

                memo[(i, j)] = res
            return memo[(i, j)]

        return dp(0, 0)