Skip to main content

动态规划

斐波那契数​

题号509. 斐波那契数

思考

  1. 动态规划五部曲
  2. 确定dp数组及其下标的含义
  3. 确定递归公式
  4. dp数组如何初始化
  5. 确定遍历顺序
  6. 举例推到dp数组
方法一 动态数组​
function fib(n: number): number {
    let dp = []
    dp[0] = 0
    dp[1] = 1
    for(let i=2;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n]
};
优化动态数组​
function fib(n: number): number {
 // 动规状态转移中，当前结果只依赖前两个元素的结果，所以只要两个变量代替dp数组记录状态过程。将空间复杂度降到O(1)
    let pre1 = 1
    let pre2 = 0
    let temp
    if (n === 0) return 0
    if (n === 1) return 1
    for(let i = 2; i <= n; i++) {
        temp = pre1
        pre1 = pre1 + pre2
        pre2 = temp
    }
    return pre1
};
方法二 递归​
function fib(n: number): number {
    if(n<2)return n
    return fib(n-1)+fib(n-2)
};

爬楼梯​

题号70. 爬楼梯

思考

  1. 没有给出状态转移方程，所以我们得学会自己推
  2. 自己推之后发现其实就是斐波那契数列
方法一 动态规划​
function climbStairs(n: number): number {
    let dp = []
    dp[1] = 1
    dp[2] = 2
    for(let i=3;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[n]
};

使用最小花费爬楼梯​

题号

思考

  1. 确定dp数组和下标的含义

  2. 到达i位置所需的最小花费值

  3. 确定递归公式

  4. 可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

    dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

    dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

    取其中最小的

  5. dp数组如何初始化

  6. 可以选择从位置0开始也可以选择从位置1开始所以

    dp[1]=0,dp[0]=0

  7. 确定遍历顺序

  8. 模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了

  9. 距离推导dp数组

方法一​
function minCostClimbingStairs(cost: number[]): number {
    let dp = []
    dp[0] = 0
    dp[1] = 0
    for(let i=2;i<=cost.length;i++){
        dp[i] = Math.min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2])
    }
    return dp[cost.length]
};

不同路径​

题号62. 不同路径

思考

  1. 要先理解dp数组的意义，dp数组指的是到这个位置的路径数目
方法一​
function uniquePaths(m: number, n: number): number {
    // 确定dp数组以及下标的含义
    const dp = new Array(m).fill(0).map(_=>[])
    // 确定递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    // 初始化dp数组
    for(let i=0;i<m;i++){
        dp[i][0]=1
    }
    for(let i=0;i<n;i++){
        dp[0][i]=1
    }
    // 确定遍历顺序
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
};

不同路径 II​

题号63. 不同路径 II

思考

  1. 障碍的后面不进行初始化
方法一​
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    let m = obstacleGrid.length,
        n = obstacleGrid[0].length
    // 确定dp数组以及下标的含义
    const dp = new Array(m).fill(0).map(_ => new Array(n).fill(0))
    // 确定递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    // 初始化dp数组
    for (let i = 0; i < m&& obstacleGrid[i][0] === 0; i++) {
        dp[i][0] = 1
    }
    for (let i = 0; i < n&& obstacleGrid[0][i] === 0; i++) {
        dp[0][i] = 1
    }
    // 确定遍历顺序
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = obstacleGrid[i][j] !== 1 ? dp[i - 1][j] + dp[i][j - 1] : 0
        }
    }
    return dp[m - 1][n - 1]
};

整数拆分​

题号343. 整数拆分

思考

  1. 首先要理解怎么让乘积最大

  2. 每个数近似大

  3. 动态规划五部曲

  4. dp数组和下标对应数目

  5. 对应i对应的最大程计

  6. 确定递归公式

  7. dp[i]: max(1 * dp[i - 1], 1 * (i - 1),2 * dp[i - 2], 2 * (i - 2), ..., (i - 2) * dp[2], (i - 2) * 2 );

  8. 初始化创建

  9. dp[2] = 1;

  10. 确定遍历顺序

  11. 输出结果

方法一​
function integerBreak(n: number): number {
    /**
        dp[i]: i对应的最大乘积
        dp[2]: 1;
        ...
        dp[i]: max(
            1 * dp[i - 1], 1 * (i - 1),
            2 * dp[i - 2], 2 * (i - 2),
            ..., (i - 2) * dp[2], (i - 2) * 2
        );
     */
    const dp: number[] = new Array(n + 1).fill(0);
    dp[2] = 1;
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j <= i / 2; j++) {
            dp[i] = Math.max(dp[i], j * dp[i - j], j * (i - j));
        }
    }
    return dp[n];
};

不同的二叉搜索树​

题号96. 不同的二叉搜索树

思考

  1. 首先要理解返回的是二叉搜索树的种数，而不是数量，所以是形状不同的
  2. 动态规划五步
  3. dp[i]：1到节点i为节点组成的二叉搜索树的个数为dp[i]
  4. 确定递推公式dp[i]=dp[j-1]*dp[i-j]，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
  5. dp数组初始化dp[0]=1
  6. 首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态
  7. 输出
方法一​
function numTrees(n: number): number {
    const dp = new Array(n+1).fill(0)
    dp[0] = 1
    dp[1] = 1

    for(let i=2;i<=n;i++){
        for(let j=1;j<=i;j++){
            dp[i] += dp[j-1]*dp[i-j]
        }
    }

    return dp[n]
};

0-1背包理论基础​

leetcode没有原题

题目：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

方法一 二维数组​
function testWeightBagProblem(
  weight: number[],
  value: number[],
  size: number
): number {
  /**
   * dp[i][j]: 前i个物品，背包容量为j，能获得的最大价值
   * dp[0][*]: u=weight[0],u之前为0，u之后（含u）为value[0]
   * dp[*][0]: 0
   * ...
   * dp[i][j]: max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
   */
  const goodsNum: number = weight.length;
  const dp: number[][] = new Array(goodsNum)
    .fill(0)
    .map((_) => new Array(size + 1).fill(0));
  for (let i = weight[0]; i <= size; i++) {
    dp[0][i] = value[0];
  }
  for (let i = 1; i < goodsNum; i++) {
    for (let j = 1; j <= size; j++) {
      if (j < weight[i]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      }
    }
  }
  return dp[goodsNum - 1][size];
}
// test
const weight = [1, 3, 4];
const value = [15, 20, 30];
const size = 4;
console.log(testWeightBagProblem(weight, value, size));
方法二 一维数组​
function testWeightBagProblem(wight, value, size) {
  const len = wight.length, 
    dp = Array(size + 1).fill(0);
  for(let i = 1; i <= len; i++) {
    for(let j = size; j >= wight[i - 1]; j--) {
      dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);
    }
  }
  return dp[size];
}


function test () {
  console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();

分割等和数组​

题号416. 分割等和子集

思考

  1. 这道题目可以抽象成0-1背包
    1. 要抽象成0-1背包需要满足
      1. 背包的体积为sum / 2
      2. 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
      3. 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
      4. 背包中每一个元素是不可重复放入。
方法一 二维数组​
function canPartition(nums: number[]): boolean {
    /**
        weightArr = nums;
        valueArr = nums;
        bagSize = sum / 2; (sum为nums各元素总和);
        按照0-1背包处理
     */
    const sum: number = nums.reduce((pre, cur) => pre + cur);
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const weightArr: number[] = nums;
    const valueArr: number[] = nums;
    const goodsNum: number = weightArr.length;
    const dp: number[][] = new Array(goodsNum)
     .fill(0)
     .map(_ => new Array(bagSize + 1).fill(0));
    for (let i = weightArr[0]; i <= bagSize; i++) {
        dp[0][i] = valueArr[0];
    }
    for (let i = 1; i < goodsNum; i++) {
        for (let j = 0; j <= bagSize; j++) {
            if (j < weightArr[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weightArr[i]] + valueArr[i]);
            }
        }
    }
    return dp[goodsNum - 1][bagSize] === bagSize;
};
方法二 一维数组​
function canPartition(nums: number[]): boolean {
    const sum: number = nums.reduce((pre, cur) => pre + cur);   
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const goodsNum: number = nums.length;
    const dp: number[] = new Array(bagSize + 1).fill(0);
    for (let i = 0; i < goodsNum; i++) {
        for (let j = bagSize; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }   
    return dp[bagSize] === bagSize;   
};