陈恒承

滚动数组

滚动数组的思想主要是用于优化 o(n)的空间复杂 使其变为 o(1),经常在动态规划中使用。
动态规划中，经常会使用到 dp[i]这个状态，这个状态经常通常用来记录某个一项的状态，如果
我们在求解的过程中，发现dp[i] 只依赖dp[i-1]或者 依赖 dp[i-2]，那么我们就可以用
可数的变量来记录它，如 pre,cur.下面，我们具体看下示例.

斐波那契数

/**
 * @param {number} N
 * @return {number}
 */
var fib = function (N) {
  //滚动数组方式
  if (N === 0) return 0;
  if (N === 1) return 1;
  /*
    F(0) = 0，F(1) = 1
    F(n) = F(n - 1) + F(n - 2)，其中 n > 1

    可以看到 
           pre2 代替 f(n-2)
           pre 代替 f(n-1)
  */

  let pre2 = 0;
  let pre1 = 1;

  let cur = 0;

  for (let i = 2; i <= N; i++) {
    cur = pre1 + pre2;
    // 这个搞成循环数组
    pre2 = pre1;
    pre1 = cur;
  }
  return cur;
};

杨辉三角

• https://leetcode-cn.com/problems/pascals-triangle-ii/

动态规划未优化

var getRow = function (rowIndex) {
  let dp = [];
  dp[0] = [1];
  dp[1] = [1, 1];
  for (let i = 2; i <= rowIndex; i++) {
    let item = [];
    item[0] = 1;
    let last = dp[i - 1];
    for (let j = 1; j < i; j++) {
      item[j] = last[j] + last[j - 1];
    }
    item[i] = 1;
    dp[i] = item;
  }

  return dp[rowIndex];
};

动态规划加数组滚动

var getRows = function(numRows) {

    if(rowIndex==0) return [1]
   if(rowIndex==1) return [1,1];

   let cur=[]

   /*
      对比未优化的代码，我们用一个pre 来记录每次迭代需要用到的前一个状态，
      而没必要把结果都存下来,由此，减少了空间复杂度，干净利落
    */
   let pre=[1,1];

   for(let i=2;i<=rowIndex;i++){
        let item=[];
        item[0]=1
        for(let j=1;j<i;j++){
            item[j]=pre[j]+pre[j-1]
        }
        item[i]=1
        cur=item
        pre=cur

   }

   return  cur