阅读 174

数据结构与算法leetcode题目解析-----动态规划(持续更新)

(声明:所有题目都是leetcode上非会员题目)

基本思想

我们先来看维基百科对动态规划的定义:

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

一个最简单的问题

讲到递归问题的时候,最经典的一个就是斐波那契数列,传统的斐波那契数列可以很容易的用递归来表示

来看leetcode上的斐波那契数列问题

leetcode 509. 斐波那契数

题目地址:斐波那契数

首先来看最基础的递归算法

/**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    if (N === 0) {
        return 0
    }
    if (N === 1) {
        return 1
    }
    return fib(N - 1) + fib(N - 2)
};
复制代码

递归算法实际上是从一个大的问题出发,一步步拆解为更小的问题,在拆解过程中,会发现很多重复子结构,所以上面的递归可以进行如下性能优化

// 缓存递归过程中已经计算过的值
var cache = [];
var fib = function(N){        
    if(cache[N]){               
       return cache[N];
    }          
    if(n <= 2){               
      cache[N] = 1;
      return 1;
    }    
    cache.push(fib(N - 1) + fib(N - 2));
    return cache[N];
}
复制代码

总体来看,递归是一种自顶向下解决问题的思想,而动态规划,则是从最小的子问题出发,一步步推广的较大的问题,是一种自底向上解决问题的思想。要注意的是[a1, a2] = [a2, a1 + a2]这行代码,就是完成了从小问题到大问题的转变,通常我们把这种转变称为状态转移,这行代码如果抽象到数学层面,就是这个问题的状态转移方程。代码如下:

/**
 * @param {number} N
 * @return {number}
 */
var fib = n => {
    if (n == 0) return 0;
    let a1 = 0;
    a2 = 1;
    for (let i = 1; i < n; i++) {
        [a1, a2] = [a2, a1 + a2];
    }
    return a2;
}
复制代码

Leetcode题目解答

leetcode 62. 不同路径

题目地址:不同路径

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const grid = []
    for (let i = 0; i < m; i++) {
        const arr = new Array(n)
        arr.fill(0)
        grid.push(arr)
    }
    grid[0][0] = 1
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i > 0 && j > 0) {
                grid[i][j] = grid[i][j - 1] + grid[i - 1][j]
            } else if (i > 0) {
                grid[i][j] = grid[i - 1][j]
            } else if (j > 0) {
                grid[i][j] = grid[i][j - 1]
            }
        }
    }
    return grid[m - 1][n - 1]
};
复制代码

leetcode 64. 最小路径和

题目地址:最小路径和

解法一:从左上角出发进行动态规划

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const m = grid.length,
    n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i > 0 && j > 0) {
                grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j])
            } else if (i > 0) {
                grid[i][j] += grid[i - 1][j]
            } else if (j > 0) {
                grid[i][j] += grid[i][j - 1]
            }
        }
    }
    return grid[m - 1][n - 1]
};
复制代码

解法二:从右下角回退进行动态规划

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const m = grid.length,
    n = grid[0].length;
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i + 1 < m && j + 1 < n) {
                grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
            } else if (i + 1 < m) {
                grid[i][j] += grid[i + 1][j];
            } else if (j + 1 < n) {
                grid[i][j] += grid[i][j + 1];
            }
        }
    }
    return grid[0][0];
};
复制代码

leetcode 70. 爬楼梯

题目地址:爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const res = []
    res[1] = 1
    res[2] = 2
    if (n === 1) {
        return 1
    }
    if (n === 2) {
        return 2
    }
    for (let i = 3; i < n + 1; i++) {
        res[i] = res[i - 1] + res[i - 2]
    }
    return res[n]
};
复制代码

leetcode 72. 编辑距离

题目地址:编辑距离

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    const n = word1.length
    const m = word2.length
    // 如果有一个字符串为空
    if (!n || !m) {
        return n + m
    }
    // DP 数组
    const dp = new Array()
    for (let i = 0; i < n + 1; i ++) {
        dp.push([])
    }
    // 边界状态初始化
    for (let i = 0; i < n + 1; i++) {
      dp[i][0] = i;
    }
    for (let j = 0; j < m + 1; j++) {
      dp[0][j] = j;
    }
    // 计算所有 DP 值
    for (let i = 1; i < n + 1; i++) {
      for (let j = 1; j < m + 1; j++) {
        let left = dp[i - 1][j] + 1;
        let down = dp[i][j - 1] + 1;
        let left_down = dp[i - 1][j - 1];
        if (word1.charAt(i - 1) !== word2.charAt(j - 1))
          left_down += 1;
        dp[i][j] = Math.min(left, down, left_down);
      }
    }
    return dp[n][m];
};
复制代码

leetcode 120. 三角形最小路径和

题目地址:三角形最小路径和

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    // 自底向上进行DP
    let dp = triangle;

    // 最后一行作为初始化的数据
    for (let i = dp.length-2; i >= 0; i--) {
        for (let j = 0; j < dp[i].length; j++) {
            // 状态转移方程
            dp[i][j] += Math.min(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    return dp[0][0]
};
复制代码

leetcode 121. 买卖股票的最佳时机

题目地址:买卖股票的最佳时机

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let curMin = prices[0]
    let sum = 0
    for (let i=0;i<prices.length;i++) {
        if (prices[i] < curMin) {
            curMin = prices[i]
            continue;
        }
        sum = Math.max(prices[i] - curMin, sum)
    }
    return sum
};
复制代码

leetcode 152. 乘积最大子数组

题目地址:乘积最大子数组

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    const len = nums.length
    let ans = nums[0]
    let prevMin = nums[0]
    let prevMax = nums[0]
    let temp1 = 0, temp2 = 0
    for (let i = 1; i < len; i++) {
        temp1 = prevMin * nums[i]
        temp2 = prevMax * nums[i]
        prevMin = Math.min(temp1, temp2, nums[i])
        prevMax = Math.max(temp1, temp2, nums[i])
        ans = Math.max(ans, prevMax)
    }
    return ans
};
复制代码

leetcode 198. 打家劫舍

题目地址:打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    if (len === 0) {
        return 0
    }
    if (len === 1) {
        return nums[0]
    }
    if (len === 2) {
        return Math.max(nums[0], nums[1])
    }
    const res = [nums[0], Math.max(nums[0], nums[1])]
    let max = Math.max(nums[0], nums[1])
    for (let i = 2; i < len; i++) {
        res[i] = Math.max(nums[i] + res[i - 2], res[i - 1])
        max = Math.max(max, res[i])
    }
    return max
};
复制代码

leetcode 221. 最大正方形

题目地址:最大正方形

dp[i][j]代表以i,j为右下角的正方形的边长

/**
 * @param {character[][]} matrix
 * @return {number}
 */
 var maximalSquare = function(matrix) {
    const m = matrix.length
    if (!m) {
        return 0
    }
    const n = matrix[0].length
    const dp = []
    let length = 0
    for (let i = 0; i < m + 1; i++) {
        dp[i] = new Array(n + 1).fill(0)
    }
    for (let i = 1; i < m + 1; i++) {
        for (let j = 1; j < n + 1; j++) {
            if (matrix[i - 1][j - 1] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
                length = Math.max(length, dp[i][j])
            } else {
                dp[i][j] = 0
            }
        }
    }
    return length * length
};
复制代码

leetcode 300. 最长上升子序列

题目地址:最长上升子序列

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    const len = nums.length
    if (len === 0) {
        return 0
    }
    if (len === 1) {
        return 1
    }
    const res = new Array(len).fill(1)
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1)
        }
    }
    res.sort((a, b) => b - a)
    return res[0]
};
复制代码

leetcode 322. 零钱兑换

题目地址:零钱兑换

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
// 用dp[i] 来表示组成金额i,需要最少的硬币数
// 硬币coin可以选择不拿 这个时候, 硬币数 = dp[i]
// 硬币coin可以选择拿 这个时候, 硬币数 = dp[i - coin] + 1
// 对于每一个coin,金额从1开始增大到amount, 不断更新 dp[i]
var coinChange = function(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity)
    // 组成金额0不需要硬币,硬币数为0
    dp[0] = 0
    for (let coin of coins ) {
        for (let i = 1; i <= amount; i++) {
            // 说明当前coin可以拿
            if (i - coin >= 0) {
                // 组成i金额需要的最小硬币数,应该是不拿coin和拿coin时硬币数的较小值
                dp[i] = Math.min(dp[i], dp[i - coin] + 1)
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
};
复制代码

leetcode 343. 整数拆分

题目地址:整数拆分

/**
 * @param {number} n
 * @return {number}
 */
 var integerBreak = function(n) {
    const arr = [0, 1]
    for (let i = 2; i < n + 1; i++) {
        for (let j = 1; j < i; j++) {
            if(!arr[i]) {
                arr[i] = 0
            }
            arr[i] = Math.max(arr[i], arr[i - j] * j, (i - j) * j)
        }
    }
    return arr[n]
};
复制代码

leetcode 416. 分割等和子集

题目地址:分割等和子集

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
 // 本质是一个求容量为sum / 2的背包问题,如果正好可以填满背包,返回true
  const sum = nums.reduce((a, b) => a + b)
  const len = nums.length
  if (sum % 2 || len < 2) {
      return false
  }
  const half = sum / 2
  // 背包
  const res = []
  for (let i = 0; i < half + 1; i++) {
    res[i] = nums[0] <= i ? nums[0] : 0
  }
  for (let i = 1; i < len; i++) {
    for (let j = half; j >= nums[i]; j--) {
        // 更新不同容量下放入的数字最大和        
        res[j] = Math.max(res[j], nums[i] + res[j - nums[i]])
    }
  }
  // 背包容量恰好填满时候返回true
  return res[half] === half
};
复制代码

leetcode 887. 鸡蛋掉落

题目地址:鸡蛋掉落

/**
 * @param {number} K
 * @param {number} N
 * @return {number}
 */
// 状态:dp[i][j] 有i个鸡蛋,j次扔鸡蛋的测得的最多楼层
// 转移方程:dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1
// 一维优化版:dp[i] = dp[i-1] + dp[i] + 1
// dp[i] 表示当前次数下使用i个鸡蛋可以测出的最高楼层
var superEggDrop = function(K, N) {
    let dp = Array(K+1).fill(0)
    let move = 0
    while (dp[K] < N){
        move++
        for (let i=K; i>0; i--){
            dp[i] = dp[i-1] + dp[i] + 1
        }
    }
    return move
};
复制代码

leetcode 983. 最低票价

题目地址:最低票价

dp[i]代表从第i天开始,到最后一天花费的最少钱数

/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function(days, costs) {
    const dp = new Array(366 + 30).fill(0)
    const len = days.length
    const max = days[len - 1]
    const min = days[0]
    let index = len - 1
    for (let i = max; i >= min; i --) {
        if (i === days[index]) {
            dp[i] = Math.min(costs[0] + dp[i + 1], costs[1] + dp[i + 7], costs[2] + dp[i + 30])
            index --
        } else {
            dp[i] = dp[i + 1]
        }
    }
    return dp[min]
};
复制代码

leetcode 1025. 除数博弈

题目地址:除数博弈

解法一. 动态规划

/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(N) {
    if(N == 1) {
        return false;
    }
    if(N == 2) {
        return true;
    } 
    const dp = new Array(N+1);
    dp[1] = false;
    dp[2] = true;
    for(let i = 3; i <= N; i++){
        dp[i] = false;
        for(let j = 1; j < i; j++){
            // 如果i-j是false,而i本身是true,直接返回true
            if(i % j === 0 && !dp[i - j]){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[N];
};
复制代码

解法二. 数学法

/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(N) {
    // 只有N为偶数时,先手才能赢
    return N % 2 === 0
};
复制代码

leetcode 面试题 17.16. 按摩师

题目地址:按摩师

/**
 * @param {number[]} nums
 * @return {number}
 */
var massage = function(nums) {
    const len = nums.length
    if (!len) {
        return 0
    }
    if (len === 1) {
        return nums[0]
    }
    if (len === 2) {
        return Math.max(nums[0], nums[1])
    }
    const res = [nums[0], Math.max(nums[0], nums[1])]
    for (let i = 2; i < len; i ++) {
        if (res[i - 2] + nums[i] > res[i - 1]) {
            res[i] = res[i - 2] + nums[i]
        } else {
            res[i] = res[i - 1]
        }
    }
    return res[len - 1]
};
复制代码