动态规划20220403

leetcode 5 .最长回文字

题目

给你一个字符串 s，找到 s 中最长的回文子串。

解题过程

定义一个函数用于寻找最长回文字的长度。逐个字符遍历，记录每一个字符周围能形成的最大回文字。因为存在“baab”式 和 “bab”式的情况，所以要以两种方式获取最大回文字，并取两者的较大值作为当前循环的结果。

var longestPalindrome = function(s) {
    let maxlen = 1,startIndex = 0;
    for(let i = 0;i<s.length;i  ){
        let len1 = fun(s,i,i)//处理“bab”式
        let len2 = fun(s,i,i 1)//处理“baab”式
        let len = Math.max(len1,len2)//获取两种情况的最大值
        //如果当前值比之前的值都要大，存储长度和起始位置
        if(len>maxlen){
            maxlen = len;
            startIndex = i-Math.floor((maxlen-1)/2)
        }
    }
    //返回寻找结果
    return s.substr(startIndex,maxlen)
};
//获得最大回文字的函数
function fun(str,left,right){
    while(left>=0 && right<=str.length && str[left] === str[right]){
        --left;
          right
    }
    return right-left-1
}

leetcode 10.正则表达式匹配

题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

• ‘.’ 匹配任意单个字符

• ‘*’ 匹配零个或多个前面的那一个元素

• 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

解题过程

注意！！！ 通配符是可以匹配零个或者多个前面的字符

常规情况

1. 当前字符不是通配符
   1. 当前s字符和p字符相同 或者 当前p字符为’.'。可以匹配任意。
2. 当前字符是通配符
   1. 通配符都不匹配的情况，通配符前一位和s当前位都不匹配，那么只能将这两位删除
   2. 根据通配符定义 匹配单个 匹配零个 匹配单个

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    //定义一个二维数组，存储当s长度为i，p长度为j时的情况
    let dp = new Array(s.length 1)
    for(let i = 0;i<dp.length;i  ){
        dp[i] = new Array(p.length 1)
    }
    //当s和p均为空时
    dp[0][0] = true
    //当s为空，p不为空时
    for(let i = 1;i<=p.length;i  ){
        if(p[i - 1] === '*' && dp[0][i - 2]){//当他为通配符时，让他匹配零个前面那个字符，这样就和p[i-2]与s[i]匹配的情况相同。如果p[i-2]与s[i]匹配情况为true，那么当前也为true
            dp[0][i] = true
        }
    }
    console.log(dp)
    for(let i = 1;i<=s.length;i  ){
        for(let j = 1;j<=p.length;j  ){
            if(s[i - 1] === p[j - 1] || p[j - 1] === '.'){
                //第一种情况——字符都能匹配/当前的p为'.'可以匹配任意单个字符
                dp[i][j] = dp[i - 1][j - 1]
            }else if(p[j - 1] === '*'){
                //第二种情况——p[j-1]为通配符
                //2.1——通配符都不匹配的情况
                if(s[i - 1] !== p[j - 2] && p[j - 2] !== '.'){
                    //通配符前一位和s当前位都不匹配，那么只能将这两位删除
                    dp[i][j] = dp[i][j - 2] 
                }else{
                    //2.2——删去两位后匹配/匹配多位/匹配上一位
                    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]
                }
            }
        }
    }
    //console.log(dp)
    return !!dp[s.length][p.length]
};

leetcode 53.最大子数组

题目

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

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

解题过程

先动态规划的默认操作，用一个数组，依次存储前前一步优化后的结果。用当前数加前一项的值等于当前的值。

因为是求最大数组和，所以如果前一项的值是小于0的，对最大和没有贡献，就舍去，加0就好；否之加前一项的值

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let dp = []
    dp[0] = nums[0]
    let max = nums[0]
    for(let i = 1;i<nums.length;i  ){
        dp[i] = nums[i]   (dp[i-1] > 0 ? dp[i-1] : 0)
        max = Math.max(max,dp[i])
    }
    return max
};

leetcode 64.最小路径和

题目

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

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

解题过程

常规的动态规划，先构建一个用于储存结果的数组。然后进行计算

var minPathSum = function(grid) {
    let row = grid.length
    let coloum = grid[0].length
    const map = new Array(row).fill().map(() => new Array(coloum).fill(0))//记录的是从(0,0)到当前格的最小路径和
    for (let i = 0; i < row; i  ) {
        for (let j = 0; j < coloum; j  ) {
            //先定义一个最小为无穷大
            let min = Infinity;
		   //先假设他是由从右往左走的，前一个的最小路径和设置为最小
            if (i - 1 >= 0) {
                min = map[i - 1][j];
            }
		   //再假设他是从上往下走的，比较是这种情况的最小路径和小还是刚刚那种情况的最小路径和下
            if (j - 1 >= 0) {
                min = Math.min(min, map[i][j - 1]);
            }
		   //如果是边界，无法查看左边那步面那步
            if (min == Infinity) {
                min = 0;
            }
		   //储存计算结果
            map[i][j] = grid[i][j]   min;
        }
    }
    return map[row-1][coloum-1]
};

leetcode 70.爬楼梯

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题过程

因为这一步可能是一步到达的，也有可能是两步到达的。所以当前位置的方案，是上一个的方案 上上个的方案

var climbStairs = function(n) {
    if(n<2){ return 1 }
    const dp = [1,1]//下标代表有多少给阶梯，值代表有多少给方法
    for(let i = 0;i < n-1;i  ){
        dp.push(dp[i] dp[i 1])
    }
    return dp[n]
};

leetcode 121.买股票的最佳时机

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题过程

买卖股票无疑就三种操作情况

• 买入
• 卖出
• 不操作

那我们可以定义四个状态

• i: 天数
• k: 交易次数，每次交易包含买入和卖出，这里我们只在买入的时候需要将 k - 1
• 0: 不持有股票
• 1: 持有股票

举例：

dp[i][k][0]//第i天 还可以交易k次 手中没有股票
dp[i][k][1]//第i天 还可以交易k次 手中有股票

状态转移方程

// 今天没有持有股票，分为两种情况
// 1. dp[i - 1][k][0]，昨天没有持有，今天不操作。 
// 2. dp[i - 1][k][1]   prices[i] 昨天持有，今天卖出，今天手中就没有股票了。
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1]   prices[i])


// 今天持有股票，分为两种情况：
// 1.dp[i - 1][k][1] 昨天持有，今天不操作
// 2.dp[i - 1][k - 1][0] - prices[i] 昨天没有持有，今天买入。
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

//最大利润就是这俩种情况的最大值

这样的方程可以多次运用于类似情况的题目

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let len = prices.length
    let dp = new Array(len).fill().map(() => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for(let i = 1;i<len;i  ){
        dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]   prices[i])
        dp[i][1] = Math.max(dp[i-1][1],-prices[i])
    }
    return dp[len-1][0]
};

更多这种题目

有很多这类题目，参考以下网站

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/mai-mai-gu-piao-wen-ti-by-chen-wei-f-uye0/

leetcode 322.零钱兑换

题目

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

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

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

解题思路

可以把amount分成一块一块， 记录达到一个amount需要的最少的硬币数，从而满足动态规划的条件。

var coinChange = function(coins, amount) {
    //判断coins只有一个的情况
    if (coins.length === 1) {
        return amount % coins[0] === 0 ? amount / coins[0] : -1
    }
    //动态规划的数组，下标代表amount数，最终的amount由很多个amount构成的
     let memo = {}
    //amount为0
    memo[0] = 0
    //最小的coins可以形成最小的amount且只需要一个硬币
    memo[Math.min(...coins)] = 1
    //开始寻找一个一个amount需要的最少硬币数
    for (let i = 1; i <= amount; i  ) {
        // 求memo[i]的最小硬币数
        let min = Number.MAX_SAFE_INTEGER
        for (let j = 0, res; j < coins.length; j  ) {
            if ((i - coins[j]) >= 0) {
                res = memo[i - coins[j]] != null ? memo[i - coins[j]]   1 : Number.MAX_SAFE_INTEGER
                min = Math.min(min, res)
            }
        }
        memo[i] = min
    }
    return memo[amount] === Number.MAX_SAFE_INTEGER ? -1 : memo[amount]
};

leetcode 343.整数拆分

题目

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

解题思路

n可以被分为n个结果，n由前面的最大乘积堆积而成。满足动态规划的条件

所以我们依次遍历n，直至到n得到结果后结束。

每一个单独的n又能被按顺序拆为1,2,…n个，这里我们给个序号为j。那么乘积就可以是j*dp[i-j],即j乘上减去这个j的最大乘积。

但我们容易忽略一种情况，就是当这个j只由(i-j)*j的情况构成，所以我们也要把这种情况放入比较

举例

10
1*9 2*8 3*7 4*6 5*5
1*9的最大值 2*8的最大值 ....

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    let dp = {}
    dp[0] = 0
    dp[1] = 1
    for(let i = 2;i<=n;i  ){
        let max = -1
        for(let j = 1;j<=i-1;j  ){
            max = Math.max(max,dp[i-j]*j,(i-j)*j)
        }
        dp[i] = max
    }
    return dp[n]
};

leetcode 486.预测赢家

题目

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

解题过程

这题也是递归，利用每次选择的差值作为结果，如果最终的结果是大于零的，证明玩家1的总和大于玩家2的总和，即胜利。否则失败``

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var PredictTheWinner = function(nums) {
    function getScore(nums,l,r){
        if(l === r) return nums[l]
        return Math.max(nums[l] - getScore(nums,l 1,r),nums[r] - getScore(nums,l,r-1))
    }
    return getScore(nums,0,nums.length-1)>=0
};

leetcode 746.使用最小花费爬楼梯

题目

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

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

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

解题思路

递归嘛，取上一步的费用 上一个格子的费用与上两步的费用 上两个格子的费用的最小值

var minCostClimbingStairs = function(cost) {
    if(cost.length<=2) return Math.min(...cost)
    let dp = new Array(cost.length)
    dp[2] = Math.min(cost[0],cost[1])
    dp[3] = Math.min(cost[0] cost[2],cost[1])
    for(let i = 4;i<=cost.length;i  ){
        dp[i] = Math.min(dp[i-1] cost[i-1],dp[i-2] cost[i-2])
    }
    console.log(dp)
    return dp[dp.length-1]
};

这篇好文章是转载于：学新通技术网