动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直到得到原问题的解。

代码示例：爬楼梯问题

// 给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，请问有多少种方案可以爬到楼顶？

public int climbingStairsDP(int n) {
  if (n == 1 || n == 2) return n;
  // 初始化dp表，用于存储子问题的解
  int[] dp = new int[n+1];
  // 初始状态：预设最小子问题的解
  dp[1] = 1;
  dp[2] = 2;
  // 状态转移：从较小子问题逐步求解较大子问题
  for (int i=3;i<=n;i++) {
    dp[i]=dp[i-1]+dp[i-2];
  }
  return dp[n];
}

常见术语

• 将数组dp称为dp表，dp[i]表示状态i对应子问题的解
• 将最小子问题对应的状态(第1阶和第2阶楼梯)称为初始状态
• 将递推公式dp[i]=dp[i-1]+dp[i-2]称为状态转移方程

空间优化

因为dp[i]只与dp[i-1]和dp[i-2]有关，所以可以只用两个变量来存储这两个值，从而节省空间。

（这种空间优化技巧称为“滚动变量”或“”）

// 空间优化后的代码示例

public int climbingStairsDPComp(int n) {
  if (n == 1 || n == 2) return n;
  // 用两个变量存储前两个状态的解
  int a = 1, b = 2;
  for (int i=3;i<=n;i++) {
    int tmp = b;
    b = a + b;
    a = tmp;
  }
  return b;
}

动态规划和分治、回溯的区别

• 分治：递归地将原问题划分为多个相互独立的子问题,直至最小子问题，并在回溯中合并子问题的解，最终得到原子问题的解
• 回溯：在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，可以将每个决策步骤之前的子序列看作一个子问题
• 动态规划：动态规划中的子问题是相互依赖的,在分解过程中会出现许多重叠子问题

动态规划特性

• 最优子结构
  （原问题的最优解是从子问题的最优解构建得来的）
  （在上面的爬楼梯的例子中，其实就是在求上n阶楼梯的最大方案数量，而求上n阶楼梯的最大方案数量是可以从子问题的最优解，也就是求n-1阶和n-2阶楼梯的最大方案数量中构建得来）
• 无后效性
  给定一个确定的状态，它的未来发展只与当前状态有关，而与过去经历的所有状态无关。
  （无后效性指当前状态确定后，后续决策仅与当前状态值有关，而与如何到达该状态的路径无关）
  （在爬楼梯的例子里，给定状态i，会发展出状态i+1和状态i+2,在做出这两种选择时，无须考虑状态i之前的状态，它们对状态i的未来没有影响）
  (举一个反例：给定一个共有n的楼梯，你每步可以上1阶或者2阶。规定当爬到第i阶时，系统自动会在第2i阶上放上障碍物，之后所有轮都不允许跳到第2i阶上。请问有多少中方案可以爬到楼顶？这个问题里，下一次跳跃依赖过去的所有状态，就不满足无后效性了)