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

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

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

斐波契数

斐波那契数 (通常用 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));

文章版权声明

 1 原创文章作者:0008,如若转载,请注明出处: https://www.52hwl.com/30558.html

 2 温馨提示:软件侵权请联系469472785#qq.com(三天内删除相关链接)资源失效请留言反馈

 3 下载提示:如遇蓝奏云无法访问,请修改lanzous(把s修改成x)

 免责声明:本站为个人博客,所有软件信息均来自网络 修改版软件,加群广告提示为修改者自留,非本站信息,注意鉴别

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年7月14日 上午12:00
下一篇 2023年7月15日