# 动态规划

动态规划

动态规划解析思路：

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤：

第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
第二步骤：找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

# 32、最长有效括号 (opens new window) （困难）（需要复习）

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    // 一、确定dp数组的含义: dp[i] 代表以 s[i] 结尾的最长有效长度，这里需要注意 s[i] 一定是等于 ')' 的，如果 s[i] === '(' 则将 dp[i] 记录为 dp[i] = 0，切记这一点，最后就是求出 dp 数组中的最大值。
    // 二、确定dp数组元素之间的关系，这里需要分情况讨论：
    //      1. s[i] === '(' 显然没办法和前面的子串组成有效子串，此时 dp[i] = 0
    //      2. s[i] === ')' 这就比较好玩了，这里又要分情况讨论了
    //          2.1 如果 dp[i-1] === 0： 
    //                  2.1.1 s[i-1] === '(' 则此时刚好和 s[i] 凑成 '()'，所以 dp[i] = (dp[i-2] || 0) + 2；需要注意 dp[i-2] 可能不存在
    //                  2.1.2 s[i-1] === ')' 则 dp[i] = 0
    //          2.2 如果 dp[i-1] !== 0 说明 s[i-1] 一定是 ')'，此时我们需要去找出 dp[i-1] 长度之前的那个符号能否和 s[i] 配对：
    //                  2.2.1 如果 s[i-dp[i-1]-1] === '(' 则 dp[i] = dp[i-1] + 2 + (dp[i-dp[i-1]-2] || 0)； 需要注意 dp[i-dp[i-1]-2] 可能不存在
    //                  2.2.2 如果 s[i-dp[i-1]-1] === ')' 则 dp[i] = 0
    // 三、确定初始值：dp[0] = 0

    var len = s.length
    if(len===0) {
        return 0
    }
    var dp = [0]
    var max = 0
    for(var i=1;i<len;i++){
       if(s[i] === '(') {
           dp[i] = 0
       } else{
           if(dp[i-1] === 0) {
                dp[i] = s[i-1] === '(' ?  (dp[i-2] || 0) + 2 : 0
           }else{
               dp[i] = s[i-dp[i-1]-1] === '(' ? dp[i-1] + 2 + (dp[i-dp[i-1]-2] || 0) : 0
           }
           max = dp[i] > max ? dp[i] : max
       }
    }
   return max
};

# 55、跳跃游戏 (opens new window) (中等)

解法一：

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    // 1. 确定dp数组元素的含义：
    // dp[i] 代表该位置能往后跳跃的最大长度，例如: nums=[10,8], dp[0] = 10,dp[1] = 9；
    // 因为从位置 0 到位置 1 需要跳跃一步，到达位置 1 后还可以往后跳跃 9 步，
    // 同时因为位置 1 本身能跳跃的步数是8，小于9 ，所以将位置 1 能跳跃的步数记为 dp[1] = 9；后续同理。
    // 2. 确定 dp 数组元素之间的关系： 
    //      2.1 正常情况：dp[i] = Math.max(dp[i-1]-1,nums[i]); dp[i-1]-1 时因为到达 dp[i] 需要减1
    //      2.2 nums = [0] 的情况已经在最后位置，返回true，但是如 nums = [0,1], 这种情况需要返回 false： if(nums[0] === 0 && nums.length > 1) return false
    //      2.3 如果 dp[i] = 0 时还没有到达最后一个位置应该返回 return false： if(dp[i] === 0 && i  !== nums.length-1) {return false}
    // 3. 确定初始值： dp[0] = num[0]
    var len = nums.length
    if(nums[0] === 0 && len > 1) return false
    var dp = [nums[0]]
    for(var i = 1; i<len; i++){
        dp[i] = Math.max(dp[i-1]-1,nums[i]);
        if(dp[i] === 0 && i  < len-1) {
            return false
        }
    }
    return true
};

解法二：空间优化

// 本题中可以直接利用nums作为 dp 数组，节省空间
var canJump = function(nums) {
    var len = nums.length
    if(nums[0] === 0 && len > 1) return false
    for(var i = 1; i<len; i++){
        nums[i] = Math.max(nums[i-1]-1,nums[i]);
        if(nums[i] === 0 && i  < len-1) {
            return false
        }
    }
    return true
};

# 62、不同路径 (opens new window) (中等)

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // 1. 定义dp数组元素的含义: 每个元素代表到达每个网格的所有路径
    // 2. 找出数组元素之间的关系式: dp[m][n] = dp[m][n-1] + dp[m-1][n]
    // 3. 找出初始值: 因为只能向下或者向右移动，所以第一行和第一列的每个dp元素的初始值都为1，只有一条路径
    var dp = []
    for(var i =0;i<m ; i++){
        dp[i] = []
        for(var j = 0;j<n;j++){
            if(j === 0) {
                dp[i][0] = 1
            } else if(i === 0 ){
                dp[0][j] = 1
            }else{
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
            }
        }
    }
    return dp[m-1][n-1]
};

# 63、不同路径 II (opens new window) （中等）

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    // 1. 定义dp数组元素的含义: 每个元素代表到达每个网格的所有路径，如果遇到某个网格是障碍物，将到达这个网格的路径dp[i][j] 设置为0
    // 2. 找出数组元素之间的关系式: dp[i][j] = obstacleGrid[i][j] === 0 ? dp[i][j-1] + dp[i-1][j] : 0
    // 3. 找出初始值: 因为只能向下或者向右移动，所以第一行和第一列的每个dp元素的初始值都为1，只有一条路径，但是如果第一行和第一列里面有障碍物，到达障碍物以及障碍物后面的网格的路径都设置为0
    var m = obstacleGrid.length
    var n = obstacleGrid[0].length
    var dp = []
    for(var i=0;i<m;i++){
        dp[i] = []
        for(var j = 0;j<n;j++){
            if(i === 0){
                dp[0][j] = obstacleGrid[0][j] === 1 || (j-1 >= 0 && dp[0][j-1] === 0) ? 0 : 1
            }else if(j === 0){
                dp[i][0] = obstacleGrid[i][0] === 1 || (i-1 >= 0 && dp[i-1][0] === 0) ? 0 : 1
            }else{
                dp[i][j] = obstacleGrid[i][j] === 0 ? dp[i][j-1] + dp[i-1][j] : 0
            }
        }
    }
    return dp[m-1][n-1]
};

# 64、最小路径和 (opens new window) （中等）

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    // 1. 定义dp数组元素的含义: 每个dp元素代表到达当前网格的路径数字最小和
    // 2. 找出数组元素之间的关系式: dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
    // 3. 找出初始值: 因为只能向下或者向右移动，所以第一行和第一列的每个dp元素的初始值都很好计算，从左往右加起来和从上往下加起来
    // 注意：这里为了节省空间直接使用grid来存储计算的结果。
    const m = grid.length
    const n = grid[0].length
    for(var i=0;i<m;i++){
        for(var j =0;j<n;j++){
            if(i === 0 && j ===0){
                grid[0][0] = grid[0][0]
            }else if(i===0){
                grid[0][j] = grid[0][j] + grid[0][j-1]
            }else if(j ===0){
                grid[i][0] = grid[i][0] + grid[i-1][0]
            }else{
                grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
            }
        }
    }
    return grid[m-1][n-1]
};

# 121、买卖股票的最佳时机 (opens new window) （简单）

解法一：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    // 1. 确定dp数组中元素的含义：因为要求的是最大利润，如果i天的价格时prices数组，很明显dp元素的含义就是这i天中卖出该股票所获得的最大利润
    // 2. 确定数组中元素的关系表达式： 假设前 i-1 天中的最低价格是min, 则 dp[i] = Math.max(dp[i-1],prices[i] - min)
    // 3. 确定初始值： dp[0] = 0
    
    var dp = [0]
    var min = prices[0]
    var len = prices.length
    for(var i = 1;i<len;i++){
        dp[i] = Math.max(dp[i-1],prices[i] - min)
        if( prices[i] < min) {
            min = prices[i]
        }
    }
    return dp[len-1]
};

解法二：空间优化

var maxProfit = function(prices) {
    var cur = [0]
    var min = prices[0]
    var len = prices.length
    for(var i = 1;i<len;i++){
        cur = Math.max(cur,prices[i] - min)
        if( prices[i] < min) {
            min = prices[i]
        }
    }
    return cur
};

# 198、打家劫舍 (opens new window)（中等）

解法一：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // 1. 确定dp数组中元素的含义：dp元素代表偷取第i个房屋时获得的最高金额
    // 2. 确定数组中元素的关系表达式：dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i])
    // 3. 确定初始值: dp[0] = num[0],dp[1] = Math.max(num[0],num[1])
    var len = nums.length
    if(len === 1) {
        return nums[0]
    }
    if(len === 2) {
        return Math.max(nums[0],nums[1])
    }
    var dp = [nums[0],Math.max(nums[0],nums[1])]
    for(var i = 2;i<nums.length;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i])
    }
    return dp[len-1]
};

解法二：

var rob = function(nums) {    
    var len = nums.length
    if(len === 1) {
        return nums[0]
    }
    if(len === 2) {
        return Math.max(nums[0],nums[1])
    }
    var preDp = nums[0],curDp = Math.max(nums[0],nums[1])
    for(var i = 2;i<nums.length;i++){
        temp = Math.max(curDp,preDp + nums[i])
        preDp = curDp
        curDp = temp
    }
    return curDp
};

# 746、使用最小花费爬楼梯 (opens new window) (简单 )

解法1：

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    // 1. 定义dp数组元素的含义: 每个元素代表的是爬到第i个阶梯的最低花费
    // 2. 找出数组元素之间的关系式: dp[i] = Math.min(dp[i-1 ] +cost[i-1],dp[i-2] + cost[i-2])
    // 3. 找出初始值: dp[0] = cost[0],dp[1] = cost[1]
    var len = cost.length
    var dp = [0,0]
    for(var i = 2;i<len;i++){
        dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2]+cost[i-2]) 
    }
    return Math.min(dp[len-1] + cost[len-1],dp[len-2] + cost[len-2])
};

解法二：

var minCostClimbingStairs = function(cost) {
    var len = cost.length
    var preDp = 0,curDp = 0,
    preValue = cost[0], 
    curValue = cost[1]
    
    for(var i = 2;i<len;i++){
        var temp = Math.min(curDp + cost[i-1], preDp +cost[i-2]) 
        preDp = curDp
        preValue = cost[i-1]
        curDp = temp
        curValue = cost[i]
    }
    return Math.min(curDp + curValue,preDp + preValue)
};

# 参考资料

告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文） (opens new window)

← leetcode 热门题目贪心算法 →

# 动态规划

# 32、最长有效括号 (opens new window) （困难）（需要复习）

# 55、跳跃游戏 (opens new window) (中等)

# 62、 不同路径 (opens new window) (中等)

# 63、 不同路径 II (opens new window) （中等）

# 64、 最小路径和 (opens new window) （中等）

# 121、买卖股票的最佳时机 (opens new window) （简单）

# 198、 打家劫舍 (opens new window)（中等）

# 746、使用最小花费爬楼梯 (opens new window) (简单 )

# 参考资料

# 62、不同路径 (opens new window) (中等)

# 63、不同路径 II (opens new window) （中等）

# 64、最小路径和 (opens new window) （中等）

# 121、买卖股票的最佳时机 (opens new window) （简单）

# 198、打家劫舍 (opens new window)（中等）