动态规划.md

核心思想

1. 将问题划分为若干个子问题，在子问题计算的基础上，逐步构建出原问题的解
2. 分治 + 最优子结构

动态规划与递归的差别

1. 无本质区别，关键是看有无最优的子问题
2. 共性：找到重复子问题
3. 差异：动态规则有最优子结构，中途可以淘汰次优解

步骤：

1. 定义状态

将原问题划分为多个子问题，定义状态表示为子问题的解，通常使用一个数组或矩阵来表示

2. 确定状态转移方程

表示从一个状态转移到另外一个状态时的转移规则。如dp[i] = dp[i-2] + dp[i-1]

3. 定义初始化状态

通过都是写在 for/while 循环中的

4. 计算原问题的解

通过计算状态之间的转移，得到最终问题的解。通常使用递归或循环计算。

用动态规划求解斐波那契数列(leetcode-509)

const fibonacci = function(count){
    const dp = [0,1]
    for (let index = 2; index <= count; index++) {
        dp[index] = dp[index-2] + dp[index-1]
    }
    return dp[count]
}

1. 定义状态: dp[index]就是i位置对应的状态(值)
2. 确定状态转移方程: dp[index] = dp[index-2] + dp[index-1]
3. 定义初始化状态: dp = [1,1]
4. 计算原问题的解: dp[count-1]

优化：状态压缩，不保留不必要的值。dp[index]的状态只与dp[index-1]和dp[index-2]有关。

const fibonacci = function(count){
    if(count <= 1) return count
    let prev = 0
    let curr = 1
    for (let index = 2; index <= count; index++) {
        [prev, curr] = [curr, prev + curr]
    }
    return curr
}

跳台阶问题(leetcode-70)

const step = function(count){
    const dp = [1,1]
    for (let index = 2; index <= count; index++) {
        dp[index] = dp[index-2] + dp[index-1];
    }
    return dp[count]
}

优化：状态压缩

const step = function(count){
    let prev = 1
    let curr = 1
    for (let index = 2; index <= count; index++) {
        [prev, curr] = [curr, prev + curr]
    }
    return curr
}

买卖股份的最佳时机(leetcode-121)

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

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

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

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

const maxProfit = function(prices){
    const dp = [0]
    let minPrice = prices[0]
    for (let index = 1; index < prices.length; index++) {
        dp[index] = prices[index] - minPrice
        minPrice = Math.min(prices[index], minPrice)
    }
    return Math.max(...dp)
}

1. 定义状态：dp[i]，在第i天卖出时可以获得的最大收益
2. 状态转移方程：dp[i] = prices[index] - minPrice
3. 定义初始化状态：dp[0]=0
4. 计算最终的解：Math.max(...dp)就是最大收益

const maxProfit = function(prices){
    const dp = [0]
    let minPrice = prices[0]
    for (let index = 1; index < prices.length; index++) {
        dp[index] = Math.max(prices[index] - minPrice, dp[index-1])
        minPrice = Math.min(prices[index], minPrice)
    }
    return dp[prices.length-1]
}

1. 定义状态：dp[i]，到第i天可以获得的最大收益
2. 状态转移方程：dp[i] = Math.max(dp[i-1],dp[i] - minPrice)
3. 定义初始化状态：dp[0]=0
4. 计算最终的解：dp[n-1]就是最大收益

优化：状态压缩。第index天的状态只与index-1天有关，因此只需要保存第index-1天的状态

const maxProfit = function(prices){
    let prevProfit = 0
    let minPrice = prices[0]
    for (let index = 1; index < prices.length; index++) {
        prevProfit = Math.max(prices[index] - minPrice, prevProfit)
        minPrice = Math.min(prices[index], minPrice)
    }
    return prevProfit
}

最大子数组和(leetcode-53)

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

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

const maxSubArray = function(number){
    const len = number.length
    const dp = [number[0]]
    for (let index = 1; index < len; index++) {
        dp[index] = Math.max(number[index], number[index]+dp[index-1])
    }
    return Math.max(...dp)
}

1. 定义状态：dp[i]，到i元素为止的连续子数组能获取的最大值
2. 状态转移方程：dp[i] = Math.max(num[i], dp[i-1] + nums[i])
3. 定义初始化状态：dp[0]=prices[0]
4. 计算最终的解：Math.max(...dp)就是最大值

优化：状态压缩。到index为止的子数组的状态只与index-1为止的子数组有关，因此只需要保存第index-1子数组的状态

const maxSubArray = function(number){
    const len = number.length
    let preValue = number[0]
    let max = preValue
    for (let index = 1; index < len; index++) {
        preValue = Math.max(number[index], number[index]+preValue)
        max = Math.max(max, preValue)
    }
    return max
}

打家劫舍(leetcode-198)

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

var rob = function(nums) {
    if(nums.length === 0) return 0
    const len = nums.length - 1
    const dp = [nums[0],Math.max(nums[0],nums[1])]
    for(let i=2;i<=len;i++){
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
    } 
    return dp[len]  
};

1. 定义状态：dp[i]，到第i家时能偷到的最大金额
2. 状态转移方程：dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
3. 定义初始化状态：dp = [nums[0],Math.max(nums[0],nums[1])]
4. 计算最终的解：dp[len]就是最大值

进行状态压缩：到第i家时，有两种选择，偷或者不偷。偷的话就需要和上上家的金额加在一起，不偷的话那偷到的最大金额就上截止上一家为止偷到的最大金额。因此只需要保存上上家时偷到的最大金额。

var rob = function(nums) {
    if(nums.length === 0) return 0
    if(nums.length === 1) return nums[0]
    const len = nums.length - 1
    let prev = nums[0]
    let max = Math.max(nums[0],nums[1])
    for(let i=2;i<=len;i++){
        let prevMax = max
        max = Math.max(max, nums[i] + prev)
        prev = prevMax
    } 
    return max 
};