动态规划Dynamic programming题型整理, since 2026-08-30

(2026.08.30 Sun Huizhou)
本文整理搜集网上资源中20种左右动态规划题型。

模式汇总

Fibonacci Sequence
Kadane's Algorithm
0/1 Knapsack
Unbounded Knapsack
Longest Common Subsequence (LCS)
Longest Increasing Subsequence (LIS)
Palindromic Subsequence
Edit Distance
Subset Sum
String Partition
Catalan Numbers
Matrix Chain Multiplication
Count Distinct Ways
DP on Grids
DP on Trees
DP on Graphs
Digit DP
Bitmasking DP
Probability DP
State Machine DP

Fibonacci Sequence

F序列适用于如下情况：该问题的解决方案取决于更小实例的解决方案。该解决方案有着清晰的递归关系，描述为F序列的经典表达F(n) = F(n-1) + F(n-2)。

70 爬楼梯 `easy`

爬楼梯需要n步到达顶端，每次爬1或2步，有多少种不同的攀登方法？
分析：设定初始条件后可通过实现F序列的公式以解决该问题。如果用经典递归方法，即更换参数调用自身，在数列变长时，会出现exceed limit的问题。该解决方案中，将中间结果保存在一个list中，最终只需要返回该序列的最后一个元素即可解决。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n in (0, 1):
            return 1
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

类似的问题还有509 Fibonacci sequence，不同的是509中的初始条件不同，F(0) = 0, F(1) = 1，70中的初始条件为F(0) = F(1) = 1，注意在代码中设定初始值。

746 最低成本爬楼梯 min cost climbing `easy`

给定一个整数序列cost[i]，代表了爬楼梯过程中，每次攀登第i个台阶，需要花费的成本，每次可以登1或2节台阶，起始点可以是index=0，也可以是index=1，计算到楼顶的最低成本。
案例1：
Input: cost = [10, 15, 20]
Output: 15
解释：从index=1开始爬，到顶的cost是15
案例2：
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
解释：从index=0开始爬
支付1，爬2级，到达index=2
支付1，爬2级，到达index=4
支付1，爬2级，到达index=6
支付1，爬2级，到达index=7
支付1，爬2级，到达index=9
支付1，爬1级，到达顶端
总cost为6

分析：该问题容易出错的地方在于，如果cost长度为n，则到达index=n-1的时候，cost已经是最后一个元素，但对答题来说到达index=n才算结束。创建一个计算总cost的序列fn，注意该序列的长度应该比cost序列的长度大1，fn的最后一个元素保存的是越过所有台阶之后到达顶端的总cost。对fn中特定元素i，该元素保存的是从i-1和i-2跳到i时的最低成本，即fn(i) = min(fn[i-1]+cost[i-1], fn[i-2]+cost[i-1])。fn的index=0，不需要爬任何台阶就可以到达的地方，所以fn[0]=0，fn的index=1，代表直接一步到达或经过index=0的台阶到达的最小值，所有fn[1]=min(cost[1], fn[0])。使用while循环。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) < 2:
            return Exception
        fn = [0] * (len(cost) + 1)
        i = 0
        while i <= len(cost):
            if i == 0:
                fn[i] = 0
                i += 1
                continue
            elif i == 1:
                fn[i] = min(cost[i], 0)
                i += 1
                continue
            else:
                fn[i] = min(fn[i-1]+cost[i-1], fn[i-2]+cost[i-2])
                i += 1
                continue
        return fn[len(cost)]

Reference

1 20 Patterns to Master Dynamic Programming by Ashish Pratap Singh, algomaster.io