目录1. 什么是动态规划2. 为什么使用一维数组3. 经典示例斐波那契数列4. 爬楼梯问题5. 零钱兑换问题6. 一维DP的通用解题步骤7. 常见问题类型类型1线性序列问题类型2背包问题一维优化类型3字符串匹配8. 实战技巧9. 总结1. 什么是动态规划动态规划Dynamic Programming简称DP是一种解决复杂问题的算法思想它通过将大问题分解为小问题并存储小问题的解来避免重复计算从而提高效率。核心思想将问题分解为子问题解决子问题通过子问题的解构建原问题的解2. 为什么使用一维数组在动态规划中我们经常使用数组来存储子问题的解。本篇文章仅介绍使用一维数组解决简单问题二维数组虽然稍微复杂但可以显示更多的信息在复杂问题中更常见。空间效率高占用内存更少代码简洁实现更简单直观适合线性问题很多问题天然适合一维表示3. 经典示例斐波那契数列我们可以从一个简单的例子开始理解一维数组在DP中的应用。问题描述计算第n个斐波那契数F(0) 0F(1) 1F(n) F(n-1) F(n-2) (n ≥ 2)暴力递归低效intfib(intn){if(n1)returnn;returnfib(n-1)fib(n-2);}一维数组DP解法intfibDP(intn){if(n1)returnn;// 创建一维数组存储结果vectorintdp(n1);// 初始化基础情况dp[0]0;dp[1]1;// 自底向上计算for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}更省空间的算法intfibOptimized(intn){if(n1)returnn;intprev20;// dp[i-2]intprev11;// dp[i-1]intcurrent;// dp[i]for(inti2;in;i){currentprev1prev2;prev2prev1;prev1current;}returncurrent;}4. 爬楼梯问题问题描述假设你正在爬楼梯每次可以爬1阶或2阶。有多少种不同的方法可以爬到第n阶该类题目的解题方法与上一种大体一致。DP分析定义状态dp[i] 表示爬到第i阶的方法数状态转移dp[i] dp[i-1] dp[i-2]初始条件dp[0] 1, dp[1] 1代码实现intclimbStairs(intn){if(n1)return1;vectorintdp(n1);dp[0]1;// 起点1种方法不动dp[1]1;// 爬1阶1种方法for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}5. 零钱兑换问题问题描述给定不同面额的硬币和一个总金额计算凑成总金额所需的最少硬币数。DP分析定义状态dp[i] 表示凑成金额i所需的最少硬币数状态转移dp[i] min(dp[i], dp[i-coin] 1)初始条件dp[0] 0其他初始化为一个大数代码实现intcoinChange(vectorintcoins,intamount){// 初始化dp数组用一个大数表示不可达vectorintdp(amount1,amount1);dp[0]0;// 金额为0时不需要硬币// 遍历所有金额for(inti1;iamount;i){// 尝试每种硬币for(intcoin:coins){if(coini){dp[i]min(dp[i],dp[i-coin]1);}}}returndp[amount]amount?-1:dp[amount];}6. 一维DP的通用解题步骤步骤1定义状态确定dp数组的含义通常dp[i]表示以位置i结尾的某种最优解dp[i]表示处理到第i个元素时的结果步骤2找出状态转移方程这是DP的核心需要分析问题如何从子问题推导斐波那契dp[i] dp[i-1] dp[i-2]爬楼梯dp[i] dp[i-1] dp[i-2]零钱兑换dp[i] min(dp[i], dp[i-coin] 1)步骤3确定初始条件设置dp数组的初始值通常dp[0]或dp[1]有特殊含义可能需要初始化多个位置步骤4确定遍历顺序根据状态转移方程决定遍历方向自底向上从前往后遍历自顶向下递归记忆化步骤5返回结果返回dp数组的最后一个元素或特定位置的元素。7. 常见问题类型类型1线性序列问题最长递增子序列最大子数组和打家劫舍问题类型2背包问题一维优化0-1背包需要逆序遍历完全背包正序遍历类型3字符串匹配编辑距离需要二维但可优化为一维8. 实战技巧技巧1空间优化很多一维DP可以优化为使用几个变量// 优化前vectorintdp(n1);// 优化后如斐波那契intprev2,prev1,current;技巧2边界处理// 检查数组越界if(icoin){dp[i]min(dp[i],dp[i-coin]1);}技巧3初始化技巧// 用大数初始化表示无穷大vectorintdp(n1,INT_MAX/2);dp[0]0;技巧4遍历顺序// 0-1背包逆序遍历防止重复使用for(intiamount;icoin;i--){dp[i]max(dp[i],dp[i-coin]value);}// 完全背包正序遍历允许重复使用for(inticoin;iamount;i){dp[i]max(dp[i],dp[i-coin]value);}9. 总结一维数组在动态规划中应用广泛掌握它需要理解状态定义明确dp[i]的含义推导转移方程找到问题的最优子结构注意边界条件正确处理初始状态考虑空间优化在必要时减少内存使用记住动态规划的核心思想是记住过去避免重复计算。一维数组正是实现这一思想的简洁工具。