91. 解码方法-数字-字母

DFS

class Solution:
    def numDecodings(self, s: str) -> int:
        def dfs(i):
            if i>=len(s):
                return 1
            ans=0
            if i+2<=len(s):
                num=int(s[i:i+2])
                if num>=10 and num<=26:
                    ans+=dfs(i+2)
            if s[i]!='0': 
                # print(ans)
                ans+=dfs(i+1)
            return ans
        if len(s)==0 or s[0]=="0": 
            return 0
        else:
            return dfs(0)

DP

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        s = ' ' + s
        f = [0] * (n + 1)
        f[0] = 1
        for i in range(1,n + 1):
            a = ord(s[i]) - ord('0')
            b = ( ord(s[i - 1]) - ord('0') ) * 10 + ord(s[i]) - ord('0')
            if 1 <= a <= 9:
                f[i] = f[i - 1]
            if 10 <= b <= 26:
                f[i] += f[i - 2]
        return f[n]

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        s = ' ' + s
        f = [0] * 3
        f[0] = 1
        for i in range(1,n + 1):
            f[i % 3] = 0
            a = ord(s[i]) - ord('0')
            b = ( ord(s[i - 1]) - ord('0') ) * 10 + ord(s[i]) - ord('0')
            if 1 <= a <= 9:
                f[i % 3] = f[(i - 1) % 3]
            if 10 <= b <= 26:
                f[i % 3] += f[(i - 2) % 3]
        return f[n % 3]

剑指 Offer 14- I. 剪绳子

（1）DFS超时

class Solution:
    def cuttingRope(self, n: int) -> int:
        def dfs(chengji,changdu):
            if changdu==n:
                ans.append(chengji)
            if changdu<n:
                for j in range(1,n):
                    dfs(chengji*j,changdu+j)
        ans=[]
        dfs(1,0)
        # print(ans)
        return max(ans)

（2）动态规划

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(2, 4):
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        return dp[n]

Python 代码（第三栏）： 由于语言特性，理论上 Python 中的变量取值范围由系统内存大小决定（无限大），因此在 Python 中其实不用考虑大数越界问题。

打家劫舍问题

1、相邻不能偷 198

大佬的解

class Solution:
    def rob(self, nums: List[int]) -> int:
        cur, pre = 0, 0
        for num in nums:
            cur, pre = max(pre + num, cur), cur
        return cur

自己的解

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0]*len(nums)
        if len(nums)<=2:
            return max(nums)
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])  # 注意
        for i in range(2,len(nums)):
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[-1]

2、头尾不能一起偷 213

class Solution:
    def rob(self, nums: [int]) -> int:
        def my_rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]

×3、树形DP

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        def _rob(root):
            if not root: return 0, 0  # 偷，不偷
            left = _rob(root.left)
            right = _rob(root.right)
            # 偷当前节点, 则左右子树都不能偷
            v1 = root.val + left[1] + right[1]
            # 不偷当前节点, 则取左右子树中最大的值
            v2 = max(left) + max(right)
            return v1, v2
        return max(_rob(root))