cumt算法设计与分析期末考速通笔记（4）｜动态规划

1 动态规划的基本写法 #

状态：表中一个位置的确切含义。转移：怎样从已经求出的小问题答案计算当前答案。完整解答需写状态定义、边界、转移、计算顺序和最终答案。

2 最大子段和 #

题意与状态 #

选取数组中连续的一段，使和最大。本节按至少选一个元素定义状态。

例：[-2,11,-4,13,-5,-2]，最优段为[11,-4,13]，和为20。不能跳过中间的-4只取11与13。

dp[i]：必须以第i个元素结尾 的最大子段和。当前位置只有重新开始和接在前面两种情况：

最终答案是所有dp的最大值20，不是最后一个dp的13。最后一个只表示必须以数组最后一项结束的最佳值。

伪代码与复杂度 #

最大子段和(a,n)：
    dp[1]=a[1]
    答案=dp[1]
    对i=2到n：
        dp[i]=max(a[i],dp[i-1]+a[i])
        答案=max(答案,dp[i])
    返回答案

约定n≥1。时间O(n)，保存全部dp空间O(n)。

全负数边界： 必须非空时返回最大负数；若题目允许空子段，则可返回0。初始化必须与题意一致。

3 0–1背包 #

题意与例题 #

n件物品，第i件重量w[i]、价值v[i]；每件最多取一次，重量为正。容量W表示最大允许重量，不要求装满。求最大总价值。

例：容量4，A重3价值5，B重2价值3，C重2价值3。最优选B+C，总重4，总价值6。

状态与边界 #

dp[i][j]：只考虑前i件物品、容量为j 时的最大价值。

• dp[0][j]=0：没有物品。
• dp[i][0]=0：容量为0。
• 最终答案为dp[n][W]。

转移方程 #

当前物品重于容量，只能不拿；否则比较拿与不拿：

如果w[i]>j：
    dp[i][j]=dp[i-1][j]
否则：
    不拿=dp[i-1][j]
    拿=dp[i-1][j-w[i]]+v[i]
    dp[i][j]=max(不拿,拿)

两种选择都读上一行i-1。 拿第i件后，剩余容量只能从前i-1件中选择，保证当前物品不被重复使用。

填表 #

以dp[3][4]为例：

不拿C：dp[2][4]=5
拿C：dp[2][4-2]+3=dp[2][2]+3=3+3=6
比较后取6。

完整伪代码 #

0-1背包(w,v,n,W)：
    建立dp[0..n][0..W]并全部初始化为0
    对i=1到n：
        对j=0到W：
            如果w[i]>j：
                dp[i][j]=dp[i-1][j]
            否则：
                dp[i][j]=max(dp[i-1][j],
                             dp[i-1][j-w[i]]+v[i])
    返回dp[n][W]

复杂度与易错点 #

共约nW个状态，每格常数次计算，时间O(nW)，二维表空间O(nW)。不是把两个循环直接写成O(n²)，两维分别是物品数n与容量W。

重量大于j时不能访问j-w[i]；不要把“前i件”当作“必须拿满i件”；容量上限不代表必须装满；题目指定回溯画树时需要按指定方法答，不能只交DP表。

4 本专题待补 #

矩阵连乘、图像压缩、最长公共子序列，以及0–1背包最优方案的通用回溯还原。后续内容继续更新本篇，不与贪心或分治混写。