【每日一题】线性DP

写在前面今天刷蓝桥杯的题目连着做了三道线性动态规划的题发现它们的核心思想居然一模一样——都是 dp[i] 由前面的几个状态转移而来。我把这三道题整理了一下从最简单的爬楼梯开始到带条件的破损楼梯再到需要决策的放置问题难度层层递进。如果你刚学动态规划或者对线性DP还有点迷糊这篇文章应该能帮到你。我会把每道题的思路、状态定义、转移方程、代码实现都讲清楚尽量不用那些让人头大的术语。一、线性动态规划是什么先说一下什么是线性DP。简单来说就是 dp[i] 的值只依赖于 dp[i-1]、dp[i-2] 等前面的状态形成一个线性的递推关系。就像多米诺骨牌推倒第一块后面的依次跟着倒。解线性DP题我习惯按这五步走拆分子问题大问题能不能拆成结构相同的小问题确定状态dp[i] 到底代表什么找状态转移方程dp[i] 由哪几个前面的状态推导而来确定初始条件dp[0]、dp[1] 这些边界值是什么实现求解循环填表返回结果。下面三道题我会按这个框架逐个分析。二、第一题基础爬楼梯斐波那契2.1 题目描述楼梯有 n 个台阶每次可以一步上 1 阶或 2 阶。一共有多少种不同的上楼方法2.2 思路分析这道题太经典了几乎就是斐波那契数列的翻版。关键问题是走到第 n 级台阶最后一步是从哪来的要么从第 n-1 级跨 1 步上来要么从第 n-2 级跨 2 步上来所以走到第 n 级的方法数 走到第 n-1 级的方法数 走到第 n-2 级的方法数。2.3 状态定义与转移方程状态dp[i]表示走到第 i 级台阶的方案数转移方程dp[i] dp[i-1] dp[i-2]初始条件dp[0] 1站在地面算一种方案dp[1] 1只有1种方法2.4 代码实现nint(input())dp[0]*(n1)dp[0]1# 地面算一种方案dp[1]1# 1级台阶只有1种方法foriinrange(2,n1):dp[i]dp[i-1]dp[i-2]print(dp[n])2.5 扩展每次可以上1~k阶如果题目改成每次可以上 1 阶、2 阶、…、k 阶转移方程就变成dp[i] dp[i-1] dp[i-2] ... dp[i-k] (i k) dp[i] dp[i-1] dp[i-2] ... dp[1] dp[0] (i k)代码可以用前缀和优化把求和部分降到 O(1)。三、第二题破损楼梯带条件的线性DP3.1 题目描述楼梯有 n 个台阶每次可以上 1 阶或 2 阶。但是有 m 个台阶是破损的不能踩。问从地面走到第 n 级有多少种方法结果对 10^97 取模3.2 思路分析这道题在基础爬楼梯上加了一个条件某些台阶不能踩。核心思路不变只是遇到破损的台阶时方案数直接设为 0。3.3 状态定义与转移方程状态dp[i]表示走到第 i 级台阶的方案数转移方程如果第 i 级是破损的dp[i] 0不能踩方案数为0否则dp[i] dp[i-1] dp[i-2]和基础版一样初始条件dp[0] 1dp[1] 1 - vis[1]如果第1级破损则dp[1]03.4 代码实现n,mmap(int,input().split())broken_listlist(map(int,input().split()))mod10**97dp[0]*(n1)# 标记数组1表示破损vis[0]*(n1)forxinbroken_list:vis[x]1# 第0个台阶就是一种方案dp[0]1# 第1个台阶如果没破损就是1种方案dp[1]1-vis[1]foriinrange(2,n1):# 如果当前台阶破损跳过dp[i]保持为0ifvis[i]1:continue# 否则和基础爬楼梯一样dp[i](dp[i-1]dp[i-2])%modprint(dp[n])3.5 关键注意点dp[0] 1这个初始化很重要。它表示站在地面算一种方案后面递推的时候 dp[2] dp[1] dp[0] 才能成立。取模题目要求对 10^97 取模每次加法后都要% mod防止数字溢出。破损台阶的处理用continue跳过dp[i] 保持默认值 0。四、第三题放置问题两种选择的线性DP4.1 题目描述有 n 个连续的位置每个位置可以放 0 或 1。要求任意连续的 1 的个数不能超过 k 个即不能出现 k1 个连续的 1。问有多少种不同的放置方案结果对 10^97 取模4.2 思路分析这道题比前两道稍微复杂一点因为每个位置有两种选择放 0 或放 1。而且放 1 的时候还要考虑前面已经连续放了几个 1不能超限制。但换个角度想如果我在第 i 个位置放 0那前面的放置方式不受限制方案数就是dp[i-1]。如果我在第 i 个位置放 1那意味着从 i-k 到 i 这 k1 个位置全放 1所以第 i-k-1 个位置必须放 0或者不存在方案数就是dp[i-k-1]。4.3 状态定义与转移方程状态dp[i]表示前 i 个位置的合法放置方案数转移方程不放置第i位放0dp[i-1]前面 i-1 个位置随便放放置第i位放1且前面k个也放1dp[i-k-1]第 i-k-1 位必须放0总和dp[i] dp[i-1] dp[i-k-1]边界情况当i k1时放 1 的方案数就是 1全放1也是一种合法方案4.4 代码实现n,kmap(int,input().split())mod10**97# dp[i] 表示前i个位置的合法放置方案数dp[0]*(n1)# 初始状态不放置也是一种方案dp[0]1foriinrange(1,n1):ifi-k-10:# 两种情况不放置 放置连续k1个1dp[i](dp[i-1]dp[i-k-1])%modelse:# i k1 时可以全放1也算一种方案# 不放置的方案 全放1的方案1种dp[i](dp[i-1]1)%modprint(dp[n])4.5 代码解释dp[0] 1前0个位置什么都不放算一种合法方案。这个初始化是后面递推的基础。i - k - 1 0只有当位置足够放 k1 个连续的 1 时才需要考虑放置这种情况。dp[i-1]第 i 位放 0前 i-1 位随便怎么放都行。dp[i-k-1]第 i-k 到 i 位放 1共 k1 个第 i-k-1 位必须放 0所以方案数等于前 i-k-1 位的方案数。1当 i k1 时全放1也是一种合法方案所以加 1。五、三题对比总结题目状态定义转移方程核心变化难度基础爬楼梯dp[i]上i级的方案数dp[i]dp[i-1]dp[i-2]无⭐⭐破损楼梯dp[i]上i级的方案数dp[i]dp[i-1]dp[i-2]破损处0加条件判断⭐⭐⭐放置问题dp[i]前i位的方案数dp[i]dp[i-1]dp[i-k-1]两种选择⭐⭐⭐⭐三道题的核心都是线性递推但难度层层递进第一题是纯递推直接套公式第二题加了条件判断遇到特殊情况处理一下第三题需要分析两种选择分别计算再合并六、线性DP的通用套路通过这三道题我总结了一个线性DP的通用解题模板# 1. 定义dp数组大小根据题目确定dp[0]*(n1)# 2. 初始化边界条件dp[0]1# 或根据题意设置# 3. 循环填表foriinrange(1,n1):# 根据题意写转移方程dp[i]...# 由dp[i-1], dp[i-2]等推导# 4. 返回答案print(dp[n])写线性DP的时候我通常会先在纸上列出前几项看看规律对不对。比如爬楼梯idp[i]说明01地面11只能跨1步2211 或 233111, 12, 2145…手动验证前几项能帮你确认状态定义和转移方程是否正确。七、常见坑和注意点dp[0] 的初始化很多题 dp[0] 1 表示空状态有一种方案这个初始化是递推的基础别漏了。数组越界访问 dp[i-1]、dp[i-2] 的时候确保 i 足够大。小数值要单独处理。取模题目要求取模的时候每次运算后都要% mod不然数字会爆炸。状态定义要清晰dp[i] 到底代表什么是前 i 个还是第 i 个这个定义不同转移方程完全不同。边界条件要单独处理比如放置问题里 i k1 的情况不能直接用通用公式。总结线性动态规划是DP中最基础也最常见的类型。它的核心思想就是当前状态由前面若干个已知状态推导而来形成一个线性的递推链条。通过这三道题你应该能感受到线性DP的套路定义状态 → 找转移方程 → 初始化边界 → 循环填表 → 返回答案掌握了这套框架大部分线性DP题目都能迎刃而解。遇到复杂一点的无非就是转移方程多几项或者加个条件判断本质不变。最后建议每道DP题都先在纸上画一画、列一列前几项确认规律对了再写代码。这比直接上手写代码效率高得多也能避免很多低级错误。如果这篇文章对你有帮助欢迎点赞收藏有任何问题可以在评论区留言我会尽量回复。后续会持续更新每日一题系列欢迎关注