「🦆TSK的博客」

Appearance

On this page

动态规划 ​

动态规划,英文: Dynamic Programming, 简称 DP
如果某一问题有很多重叠子问题，使用动态规划是最有效的
所以动态规划中每一个状态一定是由上一个状态推导出来的

🔥🔥🔥 动规五部曲:

  1. 确定 dp 数组以及下标的含义
  2. 确定递推公式-状态转移方程
  3. dp 数组的初始化
  4. 确定遍历顺序

斐波那契数 ​

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开 始，后面的每一项数字都是前面两项数字的和。

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你 n ，请计算 F(n) 。

  1. 示例 1：输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
  2. 示例 2：输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
js
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]
}

或者

js
let [a, b] = [0, 1];
for (let i = 0; i < 5; i++) {
  [a, b] = [b, a + b];
}

可以使用递归

js
function fib(n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2); // 递归
}

假如n=10，流程如下

  1. f(10) = f(9) + f(8); //分别计算f(9)和f(8)；
  2. f(9) = f(8) + f(7); //分别计算f(8)和f(7) 但是此时已经计算过 f(8) 了，如果用上面的循环的话，不会有类似的问题

爬楼梯 ​

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多 少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

  1. 示例 1：
  • 输入： 2
  • 输出： 2
  • 解释： 有两种方法可以爬到楼顶。
    • 1 阶 + 1 阶
    • 2 阶
  1. 示例 2：
  • 输入： 3
  • 输出： 3
  • 解释： 有三种方法可以爬到楼顶。
    • 1 阶 + 1 阶 + 1 阶
    • 1 阶 + 2 阶
    • 2 阶 + 1 阶
ts
function climbStairs(n: number): number {
	/**
        dp[i]: i阶楼梯的方法种数
        dp[1]: 1;
        dp[2]: 2;
        ...
        dp[i]: dp[i - 1] + dp[i - 2];
     */
	const dp: number[] = [];
	dp[1] = 1;
	dp[2] = 2;
	for (let i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
};

使用最小花费爬楼梯 ​

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

  1. 示例 1：

输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

  1. 示例 2：

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

思路 ​

  1. 确定dp数组以及下标的含义 dp[i]： 到达第i个台阶所花费的最少费用
  2. 确定递推公式 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  3. 初始化 题目要求可以从 0 / 1 台阶可以往上跳，所以初始化 dp[0] = 0, dp[1] = 0
  4. 确定遍历顺序 dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
js
var minCostClimbingStairs = function(cost) {
  const dp = [0, 0]
  for (let i = 2; i <= cost.length; ++i) {
    dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  }
  return dp[cost.length]
};

62.不同路径 ​

输入：m = 3, n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。

根据动规

  1. 确定 dp 数组以及下标的含义
    dp[i][j]表示从(0,0)出发,到 dp[i][j] 条不同的路径
  2. 确定递推公式
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
  3. dp 初始化
    dp[i][0] 都是 1,因为从 (0,0)到(i,0)的路径只有一条,那么 dp[0][j] 也都是 1

所以初始化代码是

js
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
  1. 确定遍历顺序
    这里要看一下递推公式 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就 可以了
ts
function uniquePaths(m: number, n: number): number {
  /**
        dp[i][j]: 到达(i, j)的路径数
        dp[0][*]: 1;
        dp[*][0]: 1;
        ...
        dp[i][j]: dp[i - 1][j] + dp[i][j - 1];
     */
  const dp: number[][] = new Array(m).fill(0).map(_ => []);
  // 初始化
  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 ​

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 向右 -> 向右 -> 向下 -> 向下 向下 -> 向下 -> 向右 -> 向右

与上面的不同路径相比, 增加了障碍物, 需要考虑障碍物的情况
一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理

所以初始化:

js
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

所以结果是：

js
var uniquePathsWithObstacles = function(obstacleGrid) {

    const m = obstacleGrid.length
    const n = obstacleGrid[0].length

    const dp = Array(m).fill().map(item => Array(n).fill(0))

    // 跨过障碍物
    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) {
          // obstacleGrid[i][j] === 1 说明是障碍物,说明是走不到这个地方
          dp[i][j] = obstacleGrid[i][j] === 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        }
    }

    return dp[m - 1][n - 1]
}

整数拆分 ​

给定一个正整数 n, 将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于 58。

分析 ​

  1. 确定dp 数组以及下标的含义 dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
  2. 确定递推公式
    1. 一个是j * (i - j) 直接相乘。
    2. 一个是j * dp[i - j]，相当于是拆分(i - j) 所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
  3. 确定初始值 只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1
  4. 确定遍历顺序
js
for (let i = 3; i <= n ; i++) {
     for (let j = 1; j < i - 1; j++) {
         dp[i] = Math.max(dp[i], max((i - j) * j, dp[i - j] * j));
     }
 }

至于 i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

最大值一定在中间位置

js
for (let i = 3; i <= n ; i++) {
     for (let j = 1; j < i / 2; j++) {
         dp[i] = Math.max(dp[i], max((i - j) * j, dp[i - j] * j));
     }
 }

代码 ​

js
function a(n) {
  let dp = 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], dp[i - j] * j, (i - j) * j);
    }
  }
  return dp[n];
}

Updated at: