经典150题 - 一维动态规划

70. 爬楼梯

每次可以爬 1 或 2 个台阶，求爬到 n 阶的不同方法数。

// 递推公式 dp[n] = dp[n-2] + dp[n-1]，本质是斐波那契数列，滚动变量省掉数组
var climbStairs = function (n) {
    let prevprev = 1
    let prev = 2
    if (n <= 2) {
        return n === 1 ? prevprev : prev
    }
    for (let i = 3; i <= n; i++) {
        [prev, prevprev] = [prevprev+prev, prev]
    }
 
    return prev
};

复杂度：时间 O(n)，空间 O(1)。

198. 打家劫舍

相邻房屋不能同时偷，求能偷到的最高金额。

// 状态转移 dp[i] = Max(dp[i-2]+nums[i], dp[i-1])：要么偷当前（不能偷上一家），要么不偷
var rob = function(nums) {
    if(nums.length === 1) return nums[0]
    let preprev = 0, prev = nums[0]
    for(let i = 1; i <nums.length; i++) {
        let temp = prev
        prev = Math.max(preprev + nums[i], prev)
        preprev = temp
    }
    return prev
};

复杂度：时间 O(n)，空间 O(1)。

139. 单词拆分

判断字符串 s 能否被字典中的单词拼接而成（单词可重复使用）。

// dp[i] 表示 s 前 i 个字符能否被拆分；枚举最后一枚"单词"的起点 left
var wordBreak = function(s, wordDict) {
    let set = new Set(wordDict)
    const dp = new Array(s.length+1).fill(false)
    dp[0] = true // 空串视为可拆分，是递推的基石
    for(let right = 1; right < dp.length; right++) {
        for(let left = 0 ; left < right; left++) {
            if(set.has(s.slice(left, right)) && dp[left]) {
                dp[right] = true
                break
            }
        }
    }
    // 答案是 dp[s.length]（整个串），不是 dp[s.length-1]
    return dp[s.length]
};

复杂度：时间 O(n²·L)，L 为子串均摊长度（slice + 哈希），空间 O(n)。

322. 零钱兑换

每种面值硬币无限取用，凑出 amount 的最少硬币数，凑不出返回 -1。完全背包最值型。

// dp[i] = min(dp[i-coin]+1)：金额 i 的最少硬币数由更小金额转移而来
var coinChange = function (coins, amount) {
    let dp = new Array(amount+1).fill(Infinity)
    dp[0] = 0
    for(let coin of coins) {
        for(let i=coin;i<=amount;i++) {
            dp[i] = Math.min(dp[i-coin]+1,dp[i])
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
};

复杂度：时间 O(amount × coins.length)，空间 O(amount)。详细推导见 322 零钱兑换。

300. 最长递增子序列

找出整数数组中最长严格递增子序列的长度（可不连续）。

// 状态转移 dp[i] = Math.max(dp[i], dp[j]+1)：以 nums[i] 结尾的 LIS，接在所有比它小的结尾之后
var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1)
 
    for(let i=0; i< nums.length;i++) {
        for(let j = 0;j< i;j++) {
            if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j]+1)
        }
    }
    return Math.max(...dp)
};

复杂度：时间 O(n²)，空间 O(n)；贪心 + 二分解法可优化到 O(n log n)。

相关笔记

• 多维动态规划
• 动态规划专题
• Kadane 算法
• GRD 动态规划刷题
• 动态规划与贪心基础
• Vue 3 双端对比与 Diff 算法（工业级工程应用：LIS 最长递增子序列求解最小 DOM 移动步数）