动态规划思路方法

image.png

1、设定状态

一般会对数组遍历一次， 以中间第i次为最终节点 分析情况 推出

2、思考状态转移方程

如何得到 dp[i], dp[i] 是如何从之前已经计算过的 i-1

3、考虑初始值

对初始状态赋值

4、考虑边际状态

思考边际 思考数组求值 超出情况 比如 需要dp[-1]

5、考虑输出

判断输出取的是那个状态

股票卖出最优情况

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

空间复杂度较高n²情况 导致堆内存不足

  1. /**
  2.  * @param {number[]} prices
  3.  * @return {number}
  4.  * 1:状态 第i天买进  j天卖出 所获得利润  dp[i][j]
  5.  * 2.状态转移方程：
  6.  * 比较 dp[i][j-1],dp[i-1][j],dp[i-1][j-1] 三种情况转移过来的时候
  7.  * dp[i][j] =  Math.max(dp[i][j-1]-prices[j-1]+prices[j],dp[i-1][j]+prices[i-1]-prices[i],dp[i-1][j-1]+prices[i-1]-prices[i]-prices[j-1]+prices[j])
  8.  * 上面方面 空间复杂度为n² 面对数组大的情况会导致 内存溢出
  9.  */
  10. var maxProfit = function(prices) {
  11.     const len = prices.length;
  12.     let dp = new Array(len);
  13.     for(let i=0; i < len; i++ ) {
  14.         dp[i] = new Array(len)
  15.         // 设置边际情况
  16.         dp[i][i] = 0
  17.     }
  19.     let max = 0
  21.     for(let i=0; i < len-1; i++) {
  22.         for(let j=i + 1; j < len; j++) {
  23.             if(i === 0){
  24.                 dp[i][j] = dp[i][j-1]-prices[j-1]+prices[j]
  25.             }else {
  26.                 dp[i][j] =
  27.                     Math.max(dp[i][j-1]-prices[j-1]+prices[j],dp[i-1][j]+prices[i-1]-prices[i],dp[i-1][j-1]+prices[i-1]-prices[i]-prices[j-1]+prices[j])
  28.             }
  29.             // 拿出二维数组最大值
  30.             if(max < dp[i][j]){
  31.                 max = dp[i][j]
  32.             }
  34.         }
  35.     }
  36.     // 优化 减少循环
  37.     // let max = 0;
  38.     // for(let i=0; i < len -1;i++){
  39.     //     for(let j=i + 1; j < len; j++) {
  40.     //         if(max < dp[i][j]){
  41.     //             max = dp[i][j]
  42.     //         }
  43.     //     }
  44.     // }
  45.     return max
  46. };
  47. console.log(maxProfit([7,1,5,3,6,4]))

设计进行优化 降低空间复杂度

/**
 * @param {number[]} prices
 * @return {number}
 从结合问题重新设置 状态 与转移方程
 * 1:状态 最大利润 dp[i] 当前日期卖出价钱减去   之前的最低价   可切换成更优化的设置 直接设置max
 * 2.状态转移方程
 * dp[i] = prices[i] - Math.min(...prices.slice(0,i+1))
 */
var maxProfit = function(prices) {
    const len = prices.length;
    if(len < 2){
        return 0
    }
    let dp = new Array(len);
    for(let i = 0; i < len; i++) {
        dp[i] = prices[i] - Math.min(...prices.slice(0,i+1))
    }
    return Math.max(...dp)
};

背包问题：

假设山洞里共有a,b,c,d ,e这5件宝物（不是5种宝物），它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包, 怎么装背包，可以才能带走最多的财富。

核心思路：

状态转移方程 MAX{dynamicTable(i-1,weightLimit),dynamicTable(i-1,weightLimit-w[i])+v[i])}
i:第几个物品 w[i]:对应重量 v[i]:对应价值 weightLimit:重量限制 dynamicTable:动态规划表格二维数组
状态转移方程选出以下情况的最优
情况1：不加入第i个物品
情况2 : 加入第i个物品 需要通过表格找到 i物品前 并且 限制重量为去除i重量后
tip: 与递归类似 也是利用分而治之的方法，底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案，从而解决掉整个大问题；
image.png

let w = [2,3,4,5]
let v = [3,4,5,6]

//状态转移方程 MAX{dynamicTable(i-1,weightLimit),dynamicTable(i-1,weightLimit-w[i])+v[i])}
// i:第几个物品  w[i]:对应重量   v[i]:对应价值  weightLimit:重量限制
// 状态转移方程选出以下情况的最优 情况1： 不加入第i个物品  情况2:加入第i个物品 需要通过表格找到 i物品前 并且 限制重量为去除i重量后

function dynamicProgram(wArr,vArr,weightLimit){

    //初始化动态规划表格
    let dynamicTable = new Array(wArr.length)
    const getTableValue = (k,l) =>(dynamicTable[k]&&dynamicTable[k][l]||0)

    for(let i =0;i<wArr.length;i++){
        dynamicTable[i] = new Array(weightLimit)
    }
    for(let k=0;k<wArr.length;k++){
        for(let l=0;l<weightLimit;l++){
            dynamicTable[k][l] = Math.max(getTableValue(k-1,l),l+1-wArr[k]<0?0:(getTableValue(k-1,l-wArr[k])+vArr[k]))
        }
    }
    // dynamicTable.forEach(v=>{
    //     console.log(v.join('  '))
    // })
    return dynamicTable[wArr.length-1][weightLimit-1]
}

运用场景：

瀑布流图片加载 让每一列的图片长度差趋近最小

斐波那契数列

核心思路：利用空间换时间，避免了递归的回调

//动态规划思路版

var fib = function(N) {
    let initValue = 0;
    let next = 1;
    for(let i =0;i<N;i++){
        [initValue,next] = [next,next+initValue]
    }
    return initValue
};