十五周算法训练营——普通动态规划（上）

作者：前端点线面 2023-06-13 06:51:15开发 前端 斐波那契数 （通常用 F(n) 表示）形成的周算序列称为 斐波那契数列 。该数列由 0 和 1 开始，法训后面的练营每一项数字都是前面两项数字的和。

今天是十五周算法训练营的第十一周，主要讲普通动态规划（上）专题。动态

斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的规划序列称为 斐波那契数列 。该数列由 0 和 1 开始，周算后面的法训每一项数字都是前面两项数字的和。也就是练营：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，普通其中 n > 1 给定 n ，动态请计算 F(n) 。规划

示例 1：

输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

// 1. 暴力递归的周算方法// 时间复杂度O(2^n)function fib1(n) {     if (n === 1 || n === 2) {         return 1;    }    return fib1(n - 1) + fib1(n - 2);}const startTime1 = (new Date()).getTime();console.log(fib1(30));const endTime1 = (new Date()).getTime();console.log(endTime1 - startTime1);// 2. 带备忘录的递归解法（解决了重复计算的问题）// 时间复杂度O(n)function fib2(n) {     // 利用Map存储已经求过值的结果    const map = new Map();    const helper = n => {         // 对于0和1的处理        if (n === 1 || n === 2)  {             return 1;        }        // 判断是否已经计算过，计算过则返回该值        if (map.has(n)) {             return map.get(n);        }        // 进行递归求值        map.set(n,法训 helper(n - 1) + helper(n - 2));        // 返回求得的值        return map.get(n);    }    return helper(n);}const startTime2 = (new Date()).getTime();console.log(fib1(30));const endTime2 = (new Date()).getTime();console.log(endTime2 - startTime2);// 3. 动态规划// 在备忘录启发下，可以把备忘录独立出来成为一张表（DP table），练营在该表上完成自底向上的推算function fib3(n) {     const map = new Map();    map    .set(1, 1)    .set(2, 1);    for (let i = 3; i <= n; i++) {         map.set(i, map.get(i - 1) + map.get(i - 2));    }    return map.get(n);}const startTime3 = (new Date()).getTime();console.log(fib1(30));const endTime3 = (new Date()).getTime();console.log(endTime3 - startTime3);// 4. 在动态规划基础上进行优化，由空间复杂度从O(n)优化到O(1)function fib4(n) {     if (n === 1 || n === 2) {         return 1;    }    let prev = 1;    let curr = 1;    for (let i = 3; i <= n; i++) {         const sum = prev + curr;        prev = curr;        curr = sum;    }    return curr;}const startTime4 = (new Date()).getTime();console.log(fib1(30));const endTime4 = (new Date()).getTime();console.log(endTime4 - startTime4);

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

const coins = [1, 2, 5];const amount = 19;// 1. 暴力递归，可以找出状态转移方程function coinChange1(coins, amount) {     const dp = function (amount) {         // 边界条件：当目标金额为0时结果为0        if (amount === 0) {             return 0;        }        // 边界条件：当目标金额为负数时输出-1        if (amount < 0) {             return -1;        }        // 定义结果为正无穷        let result = Infinity;        // 进行循环遍历        for (let i = 0; i < coins.length; i++) {             // 获取子问题结果            const subproblem = dp(amount - coins[i]);            // 如果子问题小于0，则子问题无解，跳出本次循环            if (subproblem < 0) {                 continue;            }            // 获取较小的结果            result = Math.min(result, 1 + subproblem);        }        return result === Infinity ? -1 : result;    };    return dp(amount);}const startTime1 = (new Date()).getTime();console.log(coinChange1(coins, amount));const endTime1 = (new Date()).getTime();console.log(endTime1 - startTime1);// 2. 带备忘录的递归// 通过备忘录消除子问题function coinChange2(coins, amount) {     const map = new Map();    const dp = function (amount) {         if (map.has(amount)) {             return map.get(amount);        }        if (amount < 0) {             return -1;        }        if (amount === 0) {             return 0;        }        let result = Infinity;        for (let i = 0; i < coins.length; i++) {             const subproblem = dp(amount - coins[i]);            if (subproblem < 0) {                 continue;            }            result = Math.min(result, 1 + subproblem);        }        map.set(amount, result === Infinity ? -1 : result);        return map.get(amount);    };    return dp(amount);}const startTime2 = (new Date()).getTime();console.log(coinChange2(coins, amount));const endTime2 = (new Date()).getTime();console.log(endTime2 - startTime2);// dp数组的迭代解法function coinChange3(coins, amount) {     const map = new Map();    // 设置边界条件    map.set(0, 0);    // 每种情况初始化为amount+1,因为最大为amount，amount + 1就相当于正无穷    for (let i = 1; i < amount + 1; i++) {         map.set(i, amount + 1);    }    for (let i = 0; i < amount + 1; i++) {         for (let j = 0; j < coins.length; j++) {             if (i - coins[j] < 0) {                 continue;            }            map.set(i, Math.min(map.get(i), 1 + map.get(i - coins[j])));        }    }    return map.get(amount) === amount + 1 ? -1 : map.get(amount);}const startTime3 = (new Date()).getTime();console.log(coinChange3(coins, amount));const endTime3 = (new Date()).getTime();console.log(endTime3 - startTime3);

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。

// 该问题是最值问题，优先考虑动态规划// 动态规划问题首先考虑是否具备最优子结构，只有具备最优子结构才能够使用动态规划// 1. 状态和选择// 本题的状态是当前在第i行j列// 选择就是向下移动或向右移动达到该目标位置// 2. dp数组含义// dp[i][j]表示grid[i][j]的最小路径和// 3. 状态转移逻辑// 为了得到dp[i][j]需要知道dp[i - 1][j]和dp[i][j - 1]哪个小，从而求得dp[i][j]// 4. base case// base case为i === 0 和 j === 0function minPathSum(grid) {     const m = grid.length;    const n = grid[0].length;    const dp = new Array(m);    for (let i = 0; i < m; i++) {         dp[i] = (new Array(n)).fill(0);    }    // base case    dp[0][0] = grid[0][0];    for (let i = 1; i < m; i++) {         dp[i][0] = dp[i - 1][0] + grid[i][0];    }    for (let j = 1; j < n; j++) {         dp[0][j] = dp[0][j - 1] + grid[0][j];    }    // 遍历dp    for (let i = 1; i < m; i++) {         for (let j = 1; j < n; j++) {             dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];        }    }    console.log(dp);    return dp[m - 1][n - 1];}const grid = [    [1,2,3]    ,[4,5,6]];console.log(minPathSum(grid));

石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例 1：

输入：piles = [5,3,4,5] 输出：true 解释： Alice 先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。 如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

• 博弈问题都这么解决

// 该问题用动态规划解决// 动态规划问题首先考虑是否具备最优子结构，只有具备最优子结构才能够使用动态规划// 1. 状态和选择// 状态：石堆的左索引、右索引、当前轮到的人// 选择：选择拿左边还是右边// 2. dp数组含义// dp[i][j]表示Alice和Blob的石子个数分别是多少// 3. 状态转移方程// 为了得到dp[i][j]需要知道dp[i + 1][j]和dp[i][j - 1],得到最优解 // 4. base case// base case就是i === j时// 因为计算dp[i][j]时需要知道dp[i+1][j],所以需要倒着进行遍历数组// 注意：在这个过程中，先手做成选择之后就变成了后手，后手在对方做完选择后，就变成了先手。这种角色互换使得可以重用之前的结果，典型的动态规划的标志function stoneGame(piles) {     const n = piles.length;    // dp数组    const dp = new Array(n);    for (let i = 0; i < n; i++) {         dp[i] = new Array(n);    }    // base case    for (let i = 0; i < n; i++) {         dp[i][i] = [piles[i], 0];    }    // 遍历dp数组    for (let i = n - 2; i >= 0; i--) {         for (let j = i + 1; j < n; j++) {             // 先手先选择左边或者右边            // 当先手进行选择后，其在其子问题中就变成了后手            const selectLeft = piles[i] + dp[i + 1][j][1];            const selectRight = piles[j] + dp[i][j - 1][1];            if (selectLeft > selectRight) {                 // 如果左侧大于右侧，则先手值就是左侧值，后手值就是其子问题的先手值                dp[i][j] = [selectLeft, dp[i + 1][j][0]];            } else {                 dp[i][j] = [selectRight, dp[i][j - 1][0]];            }        }    }    // 结果存储在dp[0][n - 1]中    const resultArr = dp[0][n - 1];    return resultArr[0] > resultArr[1];}const piles = [5, 3, 4, 5];console.log(stoneGame(piles));

最大子数组问题

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

// 既然是最值问题，肯定优先考虑动态规划// 首先判断是否具备最优子结构，只有具备最优子结构，才能通过子问题的最值得到原问题的最值【该问题肯定具备最优子结构，因为若求nums[0……i],知道其最优子结构nums[0……i - 1】肯定可以求得// 紧接着就要找正确的状态转移方程// 1. 明确状态：本题的状态就是nums[0……i]的最大子数组和// 2. 定义dp数组/函数:dp[i]表示nums[0……i]中以i位置结尾的最大子数组和// 3. 明确选择：为了获取dp[i]的最大子数组和，需要指导dp[i - 1]的最大子数组和// 4. 明确base case：此处的base case就是dp[0] = nums[0]function maxSubArray(nums) {     const dp = new Array(nums.length).fill(-Infinity);    // base case    dp[0] = nums[0];    for (let i = 1; i < nums.length; i++) {         dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];    }    return Math.max(...dp);}//  注：其实此题还可以进行状态压缩，因为dp[i]只和dp[i - 1]相关function maxSubArray1(nums) {     let pre = nums[0];    let maxVal = pre;    for (let i = 1; i < nums.length; i++) {         pre = Math.max(pre + nums[i], nums[i]);        maxVal = Math.max(maxVal, pre);    }    return maxVal;}const nums = [-2,1,-3,4,-1,2,1,-5,4];console.log(maxSubArray(nums));

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

// 因为是最值问题，优先考虑动态规划// 解决两个字符串的动态规划问题，一般都是用两个指针i、j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模// 方案一：暴力递归function minDistance1(word1, word2) {     const helper = (i, j) => {         // 确定base case，该题目的base case就是当i走完s1或j走完s2，然后将对应剩下的长度返回        if (i === -1) {             return j + 1;        }        if (j === -1) {             return i + 1;        }        if (word1[i] === word2[j]) {             // 如果两个字符一样，则跳过            return helper(--i, --j);        } else {             // 如果两个字符不一样，则在插入、删除、替换中选择最小的一个返回,然后加上该步骤操作            return Math.min(helper(i, j - 1), helper(i - 1, j), helper(i - 1, j - 1)) + 1;        }    };    return helper(word1.length - 1, word2.length - 1);}// 方案二：备忘录// 用递归暴力解决肯定会存在重叠子问题，所以需要解决重叠子问题// 通过备忘录解决子问题就是将[i, j]对应的值进行保存，然后运行的时候判断有没有function minDistance2(word1, word2) {    }// 方案三：动态规划// 因为是最值问题，优先考虑动态规划// 判断是否具备最优子结构// 找到正确的状态转移方程：// 1. 明确状态，本题中状态就是在i位置的字符串到在j位置的字符串的编辑距离// 2. 定义dp数组/函数的含义：本次dp为二维数组，表示s1[0……i]和s2[0……j]的最小编辑距离// 3. 明确选择：为了知道dp[i][j]的值，需要知道dp[i - 1][j - 1]、dp[i][j - 1]、dp[i - 1][j]的值，因为当前位置可以修改、插入、删除操作// 4. 明确base case:此处的base case就是i或j等于-1时候的值function minDistance3(word1, word2) {     // 因为当为-1的时候才是base case条件，但是数组中没有这个索引，所以整体需要扩大1    const dp = new Array(word1.length + 1);    for (let i = 0; i < dp.length; i++) {         dp[i] = (new Array(word2.length + 1)).fill(-1);    }    // 初始化base case    for (let i = 0; i < dp.length; i++) {         dp[i][0] = i;    }    for (let j = 0; j < dp[0].length; j++) {         dp[0][j] = j;    }    // 进行dp数组的遍历，在遍历过程中需要注意：    // 1. 遍历过程中所需的状态必须是已经计算出来的；    // 2. 遍历的终点必须是存储结果的那个位置，此处是dp[word1.length][word2.length]    for (let i = 1; i < dp.length; i++) {         for (let j = 1; j < dp[i].length; j++) {             // 因为整体移动了一个位置，所以比较的字符需要减一            if (word1[i - 1] === word2[j - 1]) {                 dp[i][j] = dp[i - 1][j - 1];            } else {                 dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;            }        }    }    // 最终编辑距离就是dp[word1.length][word2.length]    return dp[word1.length][word2.length];}const word1 = 'horse';const word2 = 'ros';console.log(minDistance1(word1, word2));console.log(minDistance3(word1, word2));

责任编辑：姜华 来源： 前端点线面 斐波那契数算法

(责任编辑：时尚)