动态规划（DP）是信奥最重要的算法，也是最难入门的。

从爬楼梯问题开始

问题：你每次可以爬 1 级或 2 级台阶，爬到第 n 级有多少种方法？

分析

  • 爬到第 1 级：1 种方法
  • 爬到第 2 级：2 种方法
  • 爬到第 3 级：3 种方法
  • 爬到第 n 级：dp[n-1] + dp[n-2]

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

DP 的核心思想

  1. 状态定义
  2. 状态转移
  3. 初始状态
  4. 答案

咨询 DP 学习：151 6522 2880