数组中的动态规划

509. 斐波那契数

思路

1. 递归
2. 动态规划
3. 数学公式

代码

递归

var fib = function(n) {
  if (n <= 1) {
    return n
  }
  return fib(n-1) + fib(n-2)
};

尾递归

var fib = function(n) {
  function fibTail(n, a, b) {
    if (n === 0) return b;
    return fibTail(n-1, a+b, a)
  }
  return fibTail(n, 1, 0)
};

缓存结果

// 也可以用数组或者其他数据结构缓存
var fib = function(n) {
  function fibTail(n, obj = {}) {
    if (n < 2) return n;
    return obj[n] ? obj[n] : (obj[n] = fibTail(n-1, obj) + fibTail(n-2, obj))
  }
  return fibTail(n)
};

动态规划

var fib = function(n) {
  let dp = [0, 1]
  for(let i = 2; i <= n; i ++) {
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n];
};

动态规划-空间优化

// 空间优化
var fib = function(n) {
  let a = 0, b = 1;
  for(let i = 0; i < n; i ++) {
    let sum = a + b;
    a = b;
    b = sum;
  }
  return a;
};

数学公式

var fib = function(N) {
    const s5 = Math.sqrt(5)
    return (Math.pow(.5 + s5 / 2, N) - Math.pow(.5 - s5 / 2, N)) / s5
};

矩阵-略

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29) #card=math&code=O%281%29)

70. 爬楼梯

思路

动态规划

代码

动态规划

var fib = function(n) {
  let dp = [0, 1]
  for(let i = 2; i <= n; i ++) {
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n];
};

动态规划-空间优化

// 空间优化
var fib = function(n) {
  let a = 0, b = 1;
  for(let i = 0; i < n; i ++) {
    let sum = a + b;
    a = b;
    b = sum;
  }
  return a;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29) #card=math&code=O%281%29)

338. 比特位计数

思路

Dp: res[i] = res[ i & ( i - 1 )] +1;
对于所有的数字，只有两类：
奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
举例： 0 = 0 1 = 1
2 = 10 3 = 11
偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
举例： 2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。

代码

动态规划

var countBits = function(num) {
  let res = [0];
  for(let i = 1; i <= num; i ++) {
    if (i % 2) {
       res[i] = res[i-1] + 1
    } else {
      res[i] = res[i/2]
    }
  }
  return res;
};

动态规划-位运算

var countBits = function(num) {
  let res = [0];
  for(let i = 1; i <= num; i ++) {
    res[i] = res[i & (i-1)] + 1
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

45. 跳跃游戏 II

思路

从当前位置找到能跳最远的位置，更新位置和边界

代码

DFS

var jump = function(nums) {
  let min = nums.length;

  function dfs(idx, path = []) {
    let nLen = nums.length;
    if (idx === nLen - 1) {
      min = Math.min(min, path.length)
    }
    let right = Math.min(idx + nums[idx], nLen);
    for(let i = idx; i < right; i ++) {
      dfs(i + 1, [...path, nums[i]])
    }
  }

  dfs(0, [])

  return min
};

依次遍历

var jump = function(nums) {
  let end = 0;
  let maxPosition = 0; 
  let steps = 0;
  for(let i = 0; i < nums.length - 1; i++){
      //找能跳的最远的
      maxPosition = Math.max(maxPosition, nums[i] + i); 
      if( i == end){ //遇到边界，就更新边界，并且步数加一
          end = maxPosition;
          steps++;
      }
  }
  return steps;
};

复杂度分析

时间复杂度
空间复杂度 #card=math&code=O%28N%29)

55. 跳跃游戏

思路

如果一个位置能到达，那么它左侧的所有位置都能到达

代码

var canJump = function(nums) {
  let end = 0, len = nums.length;
  for(let i = 0; i < len; i ++) {
    if (i > end) return false;
    end = Math.max(end, i + nums[i])
  }
  return true
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

198. 打家劫舍

思路

动态规划
状态转移方程 dp[i]=max(dp[i-1], dp[i-2]+cur)

代码

var rob = function(nums) {
  const dp = [0, nums[0]], len = nums.length;
  for(let i = 2; i <= len; i ++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
  }
  return dp[len]
};

var rob = function(nums) {
  let prev = 0, cur = 0;
  for(let i = 0; i < nums.length; i ++) {
    let sum = Math.max(cur, prev + nums[i]);
    prev = cur;
    cur = sum;
  }
  return cur;
};

复杂度分析

时间复杂度 )
空间复杂度 )

213. 打家劫舍 II

思路

动态规划：状态方程dp[i] = max(dp[i-1], dp[i-2] + cur)
在此基础上需要区分 第一个位置选还是不选

代码

var rob = function(nums) {
  let len = nums.length;
  const dp1 = [0, nums[0]], dp2 = [0, 0]
  for(let i = 2; i <= len; i ++) {
    // 第1家偷了
    if (i < len) {
      dp1[i] = Math.max(dp1[i-1], dp1[i-2] + nums[i-1]);
    } else {
      dp1[len] = dp1[len - 1]
    }
    // 第1家没偷
    dp2[i] = Math.max(dp2[i-1], dp2[i-2] + nums[i-1]);
  }
  // console.log(dp1, dp2)
  return Math.max(dp1[len], dp2[len])
};

var rob = function(nums) {
  let len = nums.length;
  let prev1 = 0, cur1 = 0;
  let prev2 = 0, cur2 = 0;
  if (len === 1) return nums[0]
  for(let i = 0; i < len; i ++) {
    // 第1家偷了，最后一家就不能偷
    if (i < len - 1) {
      let sum1 = Math.max(cur1, prev1 + nums[i])
      prev1 = cur1;
      cur1 = sum1;
    }
    // 第1家没偷
    if (i) {
      let sum2 = Math.max(cur2, prev2 + nums[i])
      prev2 = cur2;
      cur2 = sum2;
    }
  }
  // console.log(cur1, cur2)
  return Math.max(cur1, cur2)
};

复杂度分析

空间复杂度
时间复杂度

650. 只有两个键的键盘

91. 解码方法

639. 解码方法 II

552. 学生出勤记录 II

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

309. 最佳买卖股票时机含冷冻期

32. 最长有效括号

264. 丑数 II

313. 超级丑数

403. 青蛙过河