动态规划入门：状态与转移

// 运行环境：Node.js 14+
// 保存为 dsa-l20.js，执行：node dsa-l20.js

// 1) 爬楼梯：dp[i] = 到第 i 阶的方法数 = dp[i-1]+dp[i-2]
function climbStairs(n) {
  if (n <= 2) return n
  let a = 1, b = 2 // dp[i-2], dp[i-1]
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b]
  return b
}

// 2) 打家劫舍：dp[i] = max(不偷 i: dp[i-1], 偷 i: dp[i-2]+nums[i])
function rob(nums) {
  let prev = 0, cur = 0
  for (const x of nums) [prev, cur] = [cur, Math.max(cur, prev + x)]
  return cur
}

// 3) 0-1 背包：dp[j] = 容量 j 下最大价值；逆序更新避免重复装
function knapsack(weights, values, W) {
  const dp = new Array(W + 1).fill(0)
  for (let i = 0; i < weights.length; i++) {
    for (let j = W; j >= weights[i]; j--) {        // 必须逆序！
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i])
    }
  }
  return dp[W]
}

console.log(climbStairs(5))                    // 8
console.log(rob([2, 7, 9, 3, 1]))              // 12
console.log(knapsack([1, 3, 4], [15, 20, 30], 4)) // 35（选 1+3 重量 4 价值 35）