1.爬楼梯【L70】

1. 动态规划（滚动数组思想）

时间复杂度 O(n)

空间复杂度：O(1)

/**
 *
 * @param {*} n
 */
function climbStairs(n) {
  if (n < 1) {
    return 0;
  }
  // base case
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  // 因为状态转移只和上一次迭代和上上次迭代的结果有关，所以只用两个变量存储，不需要用数组，减少了空间
  let pre = 1;
  let cur = 2;

  for (let i = 3; i <= n; i++) {
    let sum = pre + cur;
    pre = cur;
    cur = sum;
  }
  return cur;
}

2. 动态规划（常规）

本问题其实常规解法可以分成多个子问题，爬第 n 阶楼梯的方法数量，等于 2 部分之和：

（1）爬上 n−1 阶楼梯的方法数量。因为再爬 1 阶就能到第 n 阶

（2）爬上 n−2 阶楼梯的方法数量，因为再爬 2 阶就能到第 n 阶

所以我们得到公式 dp[n] = dp[n-1] + dp[n-2]，同时需要初始化 dp[0]=1 和 dp[1]=1

时间复杂度：O(n)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  if (n <= 1) return n;

  const dp = new Array(n);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

3. 备忘录法

时间复杂度 O(n)

空间复杂度 O(n)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  let memo = {};
  const dfs = (n) => {
    // base case
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (memo[n]) return memo[n];
    memo[n] = dfs(n - 1) + dfs(n - 2);
    return memo[n];
  };
  return dfs(n);
};

2.最长递增子序列【L300】

1. 动态规划

时间复杂度 O(n^2)，n 是 nums 的长度，外层需要循环 n 次，dp[i]需要从 dp[0~i-1],所以复杂度是 O(n^2)。

空间复杂度是 O(n)，即 dp 数组的空间

（1）dp[i]的定义：dp[i]表示 i 之前包括 i 的最长上升子序列的长度。

（2）状态转移方程：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。

（3）dp[i]的初始化：每一个 i，对应的 dp[i]（即最长上升子序列）起始大小至少都是是 1

（4）确定遍历顺序

dp[i] 是有 0 到 i-1 各个位置的最长升序子序列 推导而来，那么遍历 i 一定是从前向后遍历。

j 其实就是 0 到 i-1，遍历 i 的循环里外层，遍历 j 则在内层

（5）推导 dp 数组

const lengthOfLIS = (nums) => {
  let dp = Array(nums.length).fill(1);
  let result = 1;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        //当nums[i] > nums[j]，则构成一个上升对
        dp[i] = Math.max(dp[i], dp[j] + 1); //更新dp[i]
      }
    }
    result = Math.max(result, dp[i]); //更新结果
  }

  return result;
};

2. 二分法 + 贪心

时间复杂度 O(nlogn)，n 为 nums 的长度，每次二分查找需要 logn，所以是总体的复杂度是 O(nlogn)。

空间复杂度是 O(n) ,tail 数组的开销

var lengthOfLIS = function(nums) {
  let n = nums.length;
  if (n <= 1) {
    return n;
  }
  let tail = [nums[0]]; //存放最长上升子序列数组
  for (let i = 0; i < n; i++) {
    if (nums[i] > tail[tail.length - 1]) {
      //当nums中的元素比tail中的最后一个大时 可以放心push进tail
      tail.push(nums[i]);
    } else {
      //否则进行二分查找
      let left = 0;
      let right = tail.length - 1;
      while (left < right) {
        let mid = (left + right) >> 1;
        if (tail[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      tail[left] = nums[i]; //将nums[i]放置到合适的位置，此时前面的元素都比nums[i]小
    }
  }
  return tail.length;
};

3.最长回文子序列【L516】

核心思想就是两个字“延伸”：

1. 如果一个字符串是回文串，那么在它左右分别加上一个相同的字符，那么它一定还是一个回文串，因此回文长度增加 2

2. 如果一个字符串不是回文串，或者在回文串左右分别加不同的字符，得到的一定不是回文串,因此回文长度不变，我们取[i][j-1]和[i+1][j]的较大值

/*
 * @lc app=leetcode id=516 lang=javascript
 *
 * [516] Longest Palindromic Subsequence
 */
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindromeSubseq = function(s) {
  // bbbab 返回4
  // tag : dp
  const dp = [];

  for (let i = s.length - 1; i >= 0; i--) {
    dp[i] = Array(s.length).fill(0);
    for (let j = i; j < s.length; j++) {
      if (i - j === 0) dp[i][j] = 1;
      else if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
      }
    }
  }

  return dp[0][s.length - 1];
};

4. 最大子数组和【L53 O42】

• 1. 动态规划

这有点类似「滚动数组」的思想

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

var maxSubArray = function(nums) {
  let res = nums[0];
  for (let i = 1; i < nums.length; ++i) {
    // 如果前一个的累加和小于0，就不要累加了
    if (nums[i - 1] > 0) {
      nums[i] += nums[i - 1];
    }
    res = Math.max(res, nums[i]);
  }
  return res;
};

var maxSubArray = function(nums) {
  let pre = 0,
    maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(pre + x, x);
    maxAns = Math.max(maxAns, pre);
  });
  return maxAns;
};

5. 打家劫舍【L198】

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

1. 动态规划

var rob = function(nums) {
  var len = nums.length;
  if (len < 2) {
    return nums[len - 1] ? nums[len - 1] : 0;
  }
  var current = [nums[0], Math.max(nums[0], nums[1])];
  for (var k = 2; k < len; k++) {
    current[k] = Math.max(current[k - 2] + nums[k], current[k - 1]);
  }
  return current[len - 1];
};