题型

• 输入序列 A[0,...,n-1]
• dp[i]表示为 A[0,...,i]的状态。要建立 dp[i] 与 dp[i-1]、 dp[i-2]、dp[i-3]、dp[i-4]、...、dp[0]的联系。
  • 有时候dp[i]表示为 A[0,...,i]的状态，且必须包含A[i]，此时最好用自底向上的方法，例如：题目LC300，因为此时需要回溯 dp[i] 之前的所有状态。
  • 有时候dp[i]表示为 A[0,...,i]的状态，可能包含A[i]，这时候使用自底向上或者自顶向下都可以。
  • 如果初始状态不容易确定，那么最好用自顶向下。 矩阵中最长递增路径

LC746. Min Cost Climbing Stairs

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 1：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。**因为从cost[i]开始向上走了两步所以最大值是len(cost)**

题解一

• 状态：到达台阶 i 花费的最小体力值
• 边界条件：在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。所以 dp[1]=dp[0]=0
• 状态转移方程：dp[i]=min{dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]}

$$ dp(n)=\begin{cases} 0 & \text{ if } \; n \leq 1 \\ min \left \{ dp[i-1]+cost[i-1], dp[i-2]+cost[i-2] \right \} & \text{ if } \; n >1 \end{cases} $$

自顶向下

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 字典dic保存子问题的解
        dic = {}
        def dp(n):
            # 如果求解过子问题n，则直接返回结果dic[n]
            if n in dic:
                return dic[n]
            # 边界条件
            if n<2:
                return 0
            else:
                # 状态转移方程：dp(n) = min{ dp(n-1)+cost[n-1],dp(n-2) + cost[n-2]}
                dic[n]= min(dp(n-1) + cost[n-1], dp(n-2) + cost[n-2])
            return dic[n]
        return dp(len(cost)) # 为什么是len(cost)而不是len(cost)-1。因为根据示例最后到达的是dp[n]

自低向上

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n+1)
        for i in range(2, n+1):
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        return dp[n] # 为什么是dp[n]而不是dp[n-1]。因为根据示例最后遍历完cost之后还要上一层

状态压缩

LC198. House Robber