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

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

斐波那契数

斐波那契数 （通常用 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 === 0

function 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));