算法套路十三——动态规划DP

动态规划和递归都是通过将大问题分解为较小的子问题来解决问题。它们都可以用来解决具有重叠子问题和最优子结构特性的问题。在很多情况下，动态规划算法的设计可以从递归算法开始，然后通过添加记忆化（Memoization）技术来优化递归算法。

• 递归是一种自顶向下的方法，它从原始问题开始，递归地将问题分解为较小的子问题，直到子问题可以直接解决。递归可能会导致大量的重复计算，因为它没有记录已经解决的子问题的解。
• 动态规划是一种自底向上的方法，它从最小的子问题开始，逐步解决较大的子问题，直到解决原始问题。动态规划通过存储已经解决的子问题的解（通常使用表格或数组）来避免重复计算，从而提高了算法的效率。

算法示例：LeetCode198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

递归

首先考虑直接用递归解决该题，
求偷窃到的最高金额，可以按照选或不选的思路，按照以下步骤：

1. ans1记录不偷当前房屋的最大金额
2. ans2记录不偷当前房屋的最大金额
3. 返回ans1与ans2的较大值
4. 对于1,2的最大金额采用递归来进行得到

class Solution:
    def rob(self, nums: List[int]) -> int:
        def dfs(i)-> int:
            if i >= len(nums):
                return 0
            # 不偷当前房屋
            ans1 = dfs(i + 1)
            # 偷当前房屋
            ans2 = dfs(i + 2) + nums[i]
            return max(ans1, ans2)
        return dfs(0)

按照上述的递归方式可以得到最大金额，但我们在LeetCode上会发现该方法超出时间限制。

如上图所示，我们对于选2这个分支计算了两次，那么如果房屋个数n更多，我们就会重复计算多次，这样会浪费大量的时间，故超出时间限制。

如果我们在第一次计算时，使用数组记录选择2的最大金额来保存计算结果，这样就可以避免重复计算，而这就是动态规划的精髓：递归搜索+保存计算结果=记忆化搜索。

动态规划

递推函数：dfs(i) =max (dfs(i - 1), dfs(i-2)+ nums[i])

class Solution:
    def rob(self, nums: List[int]) -> int:
    # python的@cache装饰器可以用来寄存函数对已处理参数的结果，以便遇到相同参数可以直接给出答案。
        @cache
        def dfs(i: int) -> int:
            if i >len(nums)-1: return 0
            return max(dfs(i + 1), dfs(i + 2) + nums[i])
        return dfs(0)

空间优化——滚动数组

因为递推函数dfs(i) =max (dfs(i - 1), dfs(i-2)+ nums[i]) 只依赖于前两个状态dfs(i + 1)和dfs(i + 2)，因此我们可以用f0与f1来循环记录中间结果。
当动态规划问题具有这种“滚动数组”特性时，通常可以通过使用有限数量的变量来减少空间复杂度。

class Solution:
    def rob(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for i, x in enumerate(nums):
            f0, f1 = f1, max(f1, f0 + x)
        return f1

算法练习一：LeetCode70. 爬楼梯

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

要求当前n层有多少种方法，每次可以走1或2台阶，即我们可以得出递推函数为dfs(i) =dfs(i - 1)+dfs(i-2)，且由示例可知本题可以直接进行空间优化

func climbStairs(n int) int {
    if n==1{
        return 1
    }
    f0,f1:=1,2
    for i:=2;i<n;i++{
        f0,f1=f1,f0+f1
    }
    return f1
}

算法练习二：LeetCode213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

分类讨论:

• 如果偷nums[0]，那么nums[1]和nums(n 一1]不能偷，问题变成从nums[2]到nums[n -2]的非环形版本，调用示例即198题的代码解决;
• 如果不偷nums(0]，那么问题变成从naums[1]到numsn -1]的非环形版本，同样调用示例即198题的代码解决。

func rob1(nums []int, start, end int) int {
    f0, f1 := 0, 0
    for i := start; i < end; i++ {
        f0, f1 = f1, max(f1, f0+nums[i])
    }
    return f1
}

func rob(nums []int) int {
    n := len(nums)
    return max(nums[0]+rob1(nums, 2, n-1), rob1(nums, 1, n))
}
func max(a, b int) int { if b > a { return b }; return a }