Leetcode算法之动态规划

动态规划的的四个解题步骤是：

• 定义子问题

• 写出子问题的递推关系

• 确定 DP （子问题）数组的计算顺序，或使用备忘录的递归方法

• 空间优化（可选）

  其中找出子问题的状态转移方程，问题就会简单很多，但是最难找的就是状态转移方程

198题

House Robber （小偷问题）
题解思路链接首先是定义子问题，动态规划的问题都可以将子问题扩展为全局问题，如果子问题的解法适用于全局，那么就简单了

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

代码解析，代码非常的简洁巧妙，其中max会比较记录前面子问题的最大值，如果当前子问题的值大于前面子问题的值，那么就取当前值，否则就取前面子问题的值。非常简单的思想，也是非常简单的代码，但是两个简单的东西加在一起就不简单了，真烧脑

1105题

填充书架

好烧脑，我可能不太适合这一行

题解

def minHeightShelves(books: List[List[int]], shelfWidth: int) -> int:
    n = len(books)
    dp = [inf] * (n + 1)
    dp[0] = 0
    for i, b in enumerate(books):
        curWidth = 0
        maxHeight = 0
        j = i
        while j >= 0:
            curWidth += books[j][0]
            if curWidth > shelfWidth:
                break
            maxHeight = max(maxHeight, books[j][1])
            dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight)
            j -= 1
    return dp[n]

books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
shelfWidth = 4
print(minHeightShelves(books, shelfWidth))

核心还是状态转移方程