理念

  • 多阶段决策最优解模型
  • 最优子结构
  • 无后效性

  • 重复子问题

    解题

  • 确定 dp 数组以及下标的含义

  • 确定递推公式
  • dp 数组如何初始化
  • 确定遍历顺序

  • 举例推导 dp 数组

    1. var wiggleMaxLength = function(nums) {
    2. const n = nums.length;
    3. if (n < 2) {
    4.     return n;
    5. }
    7. let up = down = 1;
    8. for (let i = 1; i < n; i++) {
    9.     if (nums[i] > nums[i - 1]) {
    10.         up = Math.max(up, down + 1);
    11.     } else if (nums[i] < nums[i - 1]) {
    12.         down = Math.max(up + 1, down);
    13.     }
    14. }
    15. return Math.max(up, down);
    16. };