算法 - 动态规划2 - 《数据结构与算法》

股票相关
121.买卖股票的最佳时机
122.买卖股票的最佳时机II
309. 最佳买卖股票时机含冷冻期
70.爬楼梯
198 打家劫舍
213.打家劫舍II
53. 最大子序和
322.零钱兑换
120 三角形最小路径和
300. 最长上升子序列
64.最小路径和
5 最长回文子串
最长公共子串
最长公共子序列
背包问题
旅行家问题

股票相关

121.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

var maxProfit = function(prices) {
    if(prices.length ===0) return 0;
    var max=0,minPrice=prices[0];
    for (let price of prices){
        if(price<minPrice) minPrice=price;
        if(price-minPrice>max) max=price-minPrice;  
    }
    return max
};

122.买卖股票的最佳时机II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。示例 2:
输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

// Solution:
// 记录每一个递增的段落。 
 const length = prices.length
  let res = 0
  for (let i = 1; i < length; i++) {
    const profit = prices[i] - prices[i - 1]
    if (profit > 0) {
      res += profit
    }
  }

309. 最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解法：DP
三种状态，rest hold sold,状态机如下：

rest

冷冻休息期只能是rest
或者buy股票

hold

hold状态只能是rest
或者
sell

sold

卖了股票之后只能休息rest
通过以上状态机，可以得出：
hold[i]=max(hold[i-1],rest[i-1]-price[i])
sold[i]= hold[i-1]+price[i]
rest[i]= max(rest[i-1],sold[i-1])
max(rest[i],sold[i])

var maxProfit = function(prices) {
    var sold = -Infinity;
    var rest = 0;
    var hold=-prices[0];

    for(var i=1;i<prices.length;i++){
        var pre_rest = rest;
        var pre_hold = hold;
        var pre_sold = sold;
        rest = Math.max(pre_rest,pre_sold);
        hold = Math.max(pre_hold,pre_rest - prices[i]);
        sold = pre_hold + prices[i]
    }

    return Math.max(rest,sold)

};

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
//第i阶的方式数量 = 到达第i-1阶的方式数量 + 到达第i-2阶的方式数量
var climbStairs = function(n) {
    var dp=[];
     dp[1] = 1;
     dp[2]=2;

    for(var i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];

};

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 。

//若选择第i个房间：第i个房间+前i-2个房间的最优解
//不选择第i个房间：前i-1个房间的最优解
//状态方程：dp[i]=max(dp[i-1],nums[i]+dp[i-2])
var rob = function(nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    var dp =[];
    dp[0]=nums[0];
    dp[1]=Math.max(nums[0],nums[1])
    for(var i=2;i<nums.length;i++){
        dp[i] = Math.max(dp[i-1],nums[i]+dp[i-2]);
    }
    return dp[nums.length -1]
};

213.打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
//此题为一个环，所以两端不可并行探索，所以分为两种情况，
//第一种 探索 0 - （length - 2）
//第二种 探索 1 - （length - 1）
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 rob = function(nums, start, end) {
        let dp=[];
        dp[start] = nums[start];
        dp[start+1] = Math.max(dp[start],nums[start+1])


        for (let i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])

        }

        return dp[end]
    }

    return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))    
};

53. 最大子序和

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

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
//dp[i]表示以第i个数字结尾的最大子段和
//状态方程：dp[i] = max(dp[i-1]+nums[i],nums[i])
//边界：以第一个数组结尾的dp[0]=nums[0]
var maxSubArray = function(nums) {
    if(nums.length == 0) return 0;
    var dp=[];
    dp[0]=nums[0];
    var max = dp[0];
    for(var i=1;i<nums.length;i++){
        dp[i] = Math.max(nums[i],dp[i-1]+nums[i] );
        if(max<dp[i]){
            max = dp[i]
        }

    }
    return max;  
};

322.零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2],
amount = 3
输出: -1 说明: 你可以认为每种硬币的数量是无限的。

//dp[i]代表金额i的最优解（使用的最小张数），根据题意：
//由金额i可知，
//金额i-1与coins[0](1元)组合
//金额i-2与coins[1](2元)组合
//金额i-5与coins[2](5元)组合
//dp[i]=min(dp[i-1],dp[i-2],dp[i-5])+1
//边界：dp[1]=1,dp[2]=1,dp[5]=1
//金额3=1+dp[3-1]=2+dp[3-1]
var coinChange = function(coins, amount) {
    var dp =[];
    var len = coins.length;
    if(len === 0) return -1;

    for(var i=0;i<amount+1;i++){
        dp[i]=-1; //初始所有金额最优解为-1
    }

    dp[0]=0;//金额0的最优解为0
    // 
    for (var i = 0; i < len; i++) {
        if (coins[i] < amount + 1) dp[coins[i]] = 1;
    }

    for(var i=1;i<amount+1;i++){
        for(var j=0;j< len;j++){ 
            if( i-coins[j] >=0 && dp[i-coins[j]] != -1){
               if (dp[i] == -1) {
                        dp[i] = dp[i - coins[j]] + 1;
                    } else {
                        dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
                    }
            }
        }
    }
    return dp[amount];
};

120 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：

[
     [2],

    [3,4],

   [6,5,7],

  [4,1,8,3]

]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

//从下往上推倒，边界值少
//dp[i][j] 从底向上三角形第i行j列最优解
//dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
//边界dp[0][0]
var minimumTotal = function(triangle) {
    if(triangle.length === 0) return 0;
    var dp=[];



    for(var i=0;i<triangle.length;i++){
        dp.push([]);
        for(var j=0;j<triangle[i].length;j++){
            dp[i].push(0);
        }
    }

    //将三角形最后一层数字复制给dp
    for(var i=0;i<dp.length;i++){
        dp[dp.length -1][i] = triangle[dp.length -1][i]  
    }

     //初始化二维数组
     // [0]
     // [0, 0]
     // [0, 0, 0]
     // [4, 1, 8, 3]

    for(var i=dp.length-2;i>=0;i--){
        for(var j=0;j<dp[i].length;j++){
            dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
        }
    }

    return dp[0][0];

};

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

//dp[i]表示以第i个元素结尾的最长上升子序列的最长长度
//边界dp[0]=1,初始化最长上升子序列LIS=1
//从1到n-1，循环i，计算dp[i]:
//从0至i-1，循环j，若nums[i] > nums[j]，说明nums[i]可放置在nums[j]的 后面，组成最长上升子序列:
//若dp[i] < dp[j] + 1:
//dp[i] = dp[j] + 1
//LIS为dp[0],dp[1],...,dp[i],...,dp[n-1]中最大的
var lengthOfLIS = function(nums) {
    if(nums.length == 0) return 0;
    var dp=new Array(nums.length);
    dp[0]=1;
    var LIS=1;
    for(var i=1;i<dp.length;i++){
        dp[i]=1;
        for(var j=0;j<i;j++){
            if(nums[i]>nums[j] && dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
            }
        }

        if(LIS<dp[i]){
            LIS=dp[i];
        }
    }
    return LIS;

};

64.最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
//dp[i][j]代表第i行j列最小路径和
//dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]
var minPathSum = function(grid) {
    if(grid.length==0) return 0;

    var dp=[];
    var row = grid.length;
    var column = grid[0].length;
    for(var i =0;i<row;i++){
        dp[i]=[];
        for(var j=0; j<column;++j ){
            dp[i][j] = 0;//初始化
        }  
    }

    [
          [0,0,0],
          [0,0,0],
          [0,0,0]
    ]

    dp[0][0]=grid[0][0];

    [
          [1,0,0],
          [0,0,0],
          [0,0,0]
    ]


    for(var i=1;i<column;i++){
        dp[0][i] = dp[0][i-1]+grid[0][i];
    }

        [1,4,5]
        [0,0,0]
        [0,0,0]

    for(var i=1;i<row;i++){
        dp[i][0] = dp[i-1][0]+grid[i][0];


        for(var j=1;j<column;j++){
            dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }

    return dp[row-1][column-1];

};

5 最长回文子串

https://www.bilibili.com/video/av73238378?from=search&seid=9606210746343043824
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
状态定义：dp[i][j]:表示从s[i...j]是否是回文串。
转移方程：
dp[i][j] = dp[i+1][j-1]==1 && (s[i]==s[j]) , j-i>1
dp[i][j] = (s[i]==s[j]) , j - i = 1
初始化：
dp[i][i] = 1
dp[i][i+1]= 1(if s[i]=s[i+1])
var longestPalindrome = function(s) {
    var len = s.length;
    var start = 0;
    var length = 1;
    var dp = [];


    for (var i = 0; i < len; i++) {
        dp.push([])
    }

    for (var i=0;i<len-1;i++){
        dp[i][i] = true;
    }
    for(var i=0;i<len-1;i++){
        if(s[i]== s[i+1]){
            dp[i][i+1]=true;
            start = i;
            length = 2;
        }
    }

    for(var n=3;n<=len;n++){  // 当前子串长度为n
        for(var i=0;i<len-n+1;i++){ // 当前子串起始位置i
            var j=i+n-1;// 子串尾端位置j. j-i=n-1
            if(s[i]==s[j]&&dp[i+1][j-1]===true){
                dp[i][j]=true;
                start =i;
                length = n;

                 // if条件句解释: 1. 当前子串长度为3时, i+1=j-i=中间的字符
                // 2. 当前子串长度为4时, i+1+1=j-i 即初始化2中检查相邻字符是否一样
                // 也就是说,以每个字符为起始的每个长度的子串都做了判断,并将结果存储在了dp[][]中
                // 下一轮长度+1时,可利用上一轮的判断结果
                // 每一个字符,都遍历了长度1~n的子串,所以时间复杂度O(n^2)
            }
        }
    }
    return s.substring(start,start+length)
}

最长公共子串

子串位置连续以两个字符串分别为行列，各个单元格字母相同：左上角加1，不同为0
寻找子序列的口诀： 如果T[i][j]来自左上角加一，则是子序列，否则向左或上回退。如果上左一样大，优先取左。
例如‘abbcc’和‘dbbcc ,最长公共子串为 bbcc

function lcs(word1,word2){
    //初始化二维数组
    var max = 0;
    var index = 0;
    var lcsarr = new Array(word1.length + 1);
    for(var i=0 ;i<=word1.length+1; ++i){
        lcsarr[i] = new Array(word2.length+1);
        for (var j=0; j<= word2.length;++j){
            lcsarr[i][j]=0;
        }
    }

    // 填充各个单元格
    for(var i=0;i<=word1.length;++i){
        for(var j=0;j<=word2.length;++j){
            if(i==0 || j==0){
                lcsarr[i][j]=0;
            } else {
                if(word1[i-1] == word2[j-1]){
                    lcsarr[i][j] = lcsarr[i-1][j-1]+1;
                } else {
                    lcsarr[i][j]=0;
                }
            }

            if(max < lcsarr[i][j]){
                max = lcsarr[i][j];
                index = i;
            }
        }

    }

    var str='';
    if(max == 0) {
        return '';
    } else {
        for (var i = index - max;i <= max;++i){
            str += word2[i];
        }
         return str;
    }

}

最长公共子序列

子串位置不连续
https://juejin.im/post/5b0c2583f265da08f50b4b33
相同左上角加1，不同取上方和左方最大
abcdf acbad 的最长公共子序列

//动态规划 -- 最长公共子序列
//!!!!  T[i][j] 计算，记住口诀：相等左上角加一，不等取上或左最大值
function longestSeq(input1,input2,n1,n2){
    var T = []; // T[i][j]表示 公共子序列长度
    for(let i=0;i<n1;i++){
        T[i] = [];
        for(let j= 0;j<n2;j++){
            if(j==0 ||i==0){
                T[i][j] = 0;
                continue;
            }
            if(input1[i] == input2[j]){
                T[i][j] = T[i-1][j-1] + 1;
            }else{
                T[i][j] = Math.max(T[i-1][j],T[i][j-1])
            }
        }
    }
    findValue(input1,input2,n1,n2,T);
    return T;
}
//!!!如果它来自左上角加一，则是子序列，否则向左或上回退。
//findValue过程，其实就是和 就是把T[i][j]的计算反过来。
function findValue(input1,input2,n1,n2,T){
    var i = n1-1,j=n2-1;
    var result = [];//结果保存在数组中
    console.log(i);
    console.log(j);
    while(i>0 && j>0){
        if(input1[i] == input2[j]){
            result.unshift(input1[i]);
            i--;
            j--;
        }else{
            //向左或向上回退
            if(T[i-1][j]>T[i][j-1]){
                //向上回退
                i--;
            }else{
                //向左回退
                j--;
            }
        }
    }
    console.log(result);
}
//两个序列，长度不一定相等, 从计算表格考虑，把input1和input2首位都补一个用于占位的空字符串
var input2 = ["","a","b","c","a","d","f"],
    input1 = ["","a","c","b","a","d"],
    n1 = input1.length,
    n2 = input2.length;
console.log(longestSeq(input1,input2,n1,n2));

背包问题

以各个商品为列，背包最大容量为行的终点，各个单元格计算如下：

cell[i][j]=max(cell[i-1][j],当前商品价值+cell[i-1][j-当前商品重量])

1.递归方案解决
2.动态规划解决
https://juejin.im/post/5affed3951882567161ad511

function max(a,b){
    return a > b ? a:b;
}
/*
* value 商品价值数组 size商品重量数组，capacity背包最大容量，n商品数量
*/
function dKnap(capacity,size,value,n){
    //初始化二维数组
    var K=[];
    for(var i=0;i<=capacity+1;i++){
        K[i]=[];
    }

    for(var i = 0; i <= n ; i++){ //各个商品
        for(var j=0;j<=capacity;j++){ //容量单位
            if(i==0 || j==0){
                K[i][j] = 0;
            } else if (size[i-1]<=j){//大小为size[i-1]的商品可以放到j容量中
            K[i][j] = max(K[i-1][j],value[i-1]+K[i-1][j-size[i-1]]);

            } else {//大小为size[i-1]不能放到背包
                K[i][j] = K[i-1][j];
            }
            document.write(K[i][j]);
            document.write("...");
        }
         document.write("<br>");
    }
    return K[n][capacity]

}
var value=[1500,2000,3000];
var size=[1,3,4];
var capacity=4;
var n =3;
dKnap(capacity,size,value,n);

旅行家问题

思路同背包问题