算法刷题模型整理（六）

动态规划

LC509 斐波那契数

解题模型：

​ 线性

核心思路：

​ 建立一维dp数组，dp[i]对应F(i)，初始化dp[0]=0，dp[1]=1。然后开始推导，dp[i]=dp[i-1]+dp[i-2]

易错点：

• 遍历时i从2开始，0和1已经初始化
• 本题可以简化，发现每次访问的只有前两个数，所以dp数组可以简化为三个变量，存放前两个数和自身

LC070 爬楼梯

解题模型：

​ 线性

核心思路：

​ 思路与LC509斐波那契数相似，到达第i阶楼梯的方法数等于第i-1和第i-2的方法之和

易错点：

• 当楼梯阶数小于2时直接返回阶数本身，优化性能
• 只需三个变量即可，无需创建整个数组

LC343 整数拆分

解题模型：

​ 线性

核心思路：

​ 创建dp数组，dp[0]和dp[1]分别初始化为0和1，dp[i]代表i拆分的最大乘积，将i拆分成j和i-j后，有继续拆分i-j和直接取i，i-j两种选择，取两者中较大的一个，拆分i-j的最大乘积查询dp数组可得。两层循环，第一层为i，第二层为j，推导直到i等于给定正整数

易错点：

• i从2开始
• 数组初始化大小为给定正整数加1

LC322 零钱兑换

解题模型：

​ 完全背包

核心思路：

​ 创建dp数组，dp[0]=0，dp[i]=凑成i的最小钱币数，凑成i的最小钱币数等于dp[i-某个面额]+1，双层循环第一层遍历dp数组，第二层遍历钱币面额，若退出时维护的最小值minN还是原大小则赋值dp[i]为-1，否则dp[i]赋值为minN，直到推到总金额

易错点：

• minN初始化为目标总金额+1，最小钱币数一定这个数，因为钱币面额最小为1
• 内层循环中，如果目标金额小于当前面额或dp[i-当前面额]为-1，则内层进入下一次循环

LC416 分割等和子集

解题模型：

​ 0-1背包

核心思路：

​ 算出所有数字的和sum，若sum是奇数，说明不可分割，可直接返回false。选取数字只需能使和等于sum/2即可。创建二维dp数组，i代表将0~i的数字加入考虑，j代表目标数字。若选取当前数字，则dp[i][j]=dp[i-1][j-nums[i]]，若不选取，则dp[i][j]=dp[i-1][j]

易错点：

• 二维dp可以优化为滚动数组
• j小于nums[i]时直接进入下一次循环，dp[i][j]=dp[i-1][j]

LC300 最长递增子序列

解题模型：

​ 线性

核心思路：

​ 创建dp数组，dp[i]表示考虑下标0~i的元素时，最后一个元素为i的最长递增子序列，当i的元素大于j时，dp[i]等于max(dp[j]+1, dp[i])，遍历完整个数组后，答案为dp数组中最大值

易错点：

• dp数组初始化为1
• 传入数组长度小于2时，答案即为数组长度

LC072 编辑距离

解题模型：

​ 线性

核心思路：

​ dp数组横坐标i代表每个字符串到达对应word1子串所需步数，纵坐标j代表到达对应word2子串所需步数，下标0为空串，当i=word1.length()，j=word2.length()时对应值即为答案，初始化dp[0][i]=i,dp[i][0]=i，left等于dp[i-1][j]，up等于dp[i][j-1]，leftUp等于dp[i-1][j-1]，word1[i-1]!=word2[j-1]时dp[i][j]=min(left+1,min(up+1,leftUp+1))，否则 dp[i][j]=min(left+1,min(up+1,leftUp))

易错点：

• 下标范围是[0~字符串长度+1]
• 注意leftUp在什么时候要+1