动态规划

https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/

不少同学对动态规划还处于朦胧状态，我特意录了一期视频（https://www.bilibili.com/video/BV13Q4y197Wg），讲一讲动态规划解题方法论，这里详细介绍了动规五部曲，相信结合本篇题解，会对你学习动态规划有所帮助。

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

我们来分析一下，动规五部曲：

定义一个一维数组来记录不同楼层的状态

确定dp数组以及下标的含义
dp[i]： 爬到第i层楼梯，有dp[i]种方法

确定递推公式
如果可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！

所以dp[i] = dp[i - 1] + dp[i - 2] 。

在推导dp[i]的时候，一定要时刻想着dp[i]的定义，否则容易跑偏。

这体现出确定dp数组以及下标的含义的重要性！

dp数组如何初始化
在回顾一下dp[i]的定义：爬到第i层楼梯，有dp[i]中方法。

那么i为0，dp[i]应该是多少呢，这个可以有很多解释，但都基本是直接奔着答案去解释的。

例如强行安慰自己爬到第0层，也有一种方法，什么都不做也就是一种方法即：dp[0] = 1，相当于直接站在楼顶。

但总有点牵强的成分。

那还这么理解呢：我就认为跑到第0层，方法就是0啊，一步只能走一个台阶或者两个台阶，然而楼层是0，直接站楼顶上了，就是不用方法，dp[0]就应该是0.

其实这么争论下去没有意义，大部分解释说dp[0]应该为1的理由其实是因为dp[0]=1的话在递推的过程中i从2开始遍历本题就能过，然后就往结果上靠去解释dp[0] = 1。

从dp数组定义的角度上来说，dp[0] = 0 也能说得通。

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化！

我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。

所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。

确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

举例推导dp数组
举例当n为5的时候，dp table（dp数组）应该是这样的

!70.爬楼梯

如果代码出问题了，就把dp table 打印出来，看看究竟是不是和自己推导的一样。

此时大家应该发现了，这不就是斐波那契数列么！

唯一的区别是，没有讨论dp[0]应该是什么，因为dp[0]在本题没有意义！

最大子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if (!nums.length) {
        return;
    };
  let fast=nums[0];
  let slow=nums[0];
  for(let i=1;i<nums.length;i++){
      fast=Math.max(nums[i],fast+nums[i])
      slow=Math.max(fast,slow)
  }
  return slow
};

环形子数组的最大和

最大子序和减去最小子序和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubarraySumCircular = function(nums) {
//  let len=nums.length;
 let sum=0
 let pre=0;
 let pre2=0;
 let maxAns=nums[0];
 let minAns=0;
 nums.forEach((x)=>{
 pre=Math.max(pre+x,x)
 pre2=Math.min(pre2+x,x)
 maxAns=Math.max(pre,maxAns)
 minAns=Math.min(pre2,minAns)
 sum=sum+x
 })
if(maxAns<0) return maxAns
return Math.max(maxAns,sum-minAns)
};

斐波那契数

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
 let first=0
 let second=1
 let sum=1
 if(n==0){
     return 0
 }
 else if((n==1)||(n==2)){
     return 1
 }
 else{
     for(i=3;i<=n;i++){
        first=second
        second=sum
        sum=first+second

     }
     return sum
 }
};

爬楼梯

 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n==1){
        return 1
    }
    else if(n==2){
        return 2
    }
    let dp=new Array(n)
    dp[1]=1
    dp[2]=2
    for(let i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2]
        }
    return dp[n]
}

使用最小花费爬楼梯

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    let n=cost.length
    let dp=new Array(n+1)
    dp[0]=dp[1]=0
    for (let i=2;i<n+1;i++){
        dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    }
    return dp[n]
};

打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
if(nums.length==1){
    return nums[0]
}
let result=0
let preOne=nums[0]
let preTwo=0
 for(let i= 1; i < nums.length; i++){
        result = Math.max(preTwo + nums[i], preOne);
        preTwo = preOne;
        preOne= result
    }
    return result
};

打家劫舍 II

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
if(nums.length==1){
    return nums[0]
}
if(nums.length==2){
    return Math.max(nums[0],nums[1])
}
//不抢第一个
let result1=0
let preOne1=nums[1]
let preTwo1=0
 for(let i= 2; i < nums.length; i++){
        result1 = Math.max(preTwo1 + nums[i], preOne1);
        preTwo1 = preOne1;
        preOne1= result1
    }
//不抢最后一个
let result2=0
let preOne2=nums[0]
let preTwo2=0
 for(let i= 1; i < nums.length-1; i++){
        result2 = Math.max(preTwo2 + nums[i], preOne2);
        preTwo2 = preOne2;
        preOne2= result2
    }
return Math.max(result1,result2)
};

删除并获得点数

/**
 * @param {number[]} nums
 * @return {number}
 */
var deleteAndEarn = function(nums) {
let max_nums_val=1;
for(let i=0;i<nums.length;i++){
    max_nums_val=Math.max(max_nums_val,nums[i])
}
let array=new Array(max_nums_val+1).fill(0)
for(let i=0;i<nums.length;i++){
   array[nums[i]]++
}
let result=0 //定义结果
let preOne=array[1] //dp[i-1]
let preTwo=0 //dp[i-2]
if(array.length==2){
    return array[1]
}
for(let i=2;i<array.length;i++){
    result=Math.max(preTwo+array[i]*i,preOne)
    preTwo=preOne
    preOne=result
}
return result

};

跳跃游戏

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
 let after=0
 for(i=0;i<nums.length-1;i++){
     after=Math.max(i+nums[i],after)
     if(nums[i]==0&&after==i)
        return false
 }
 if(after<nums.length-1)
    return false
    else
    return true

};

跳跃游戏 II

var jump = function(nums) {
    let dp=new Array(nums.length).fill(0)
    for(let i=0;i<nums.length-1;i++){
        if(i+nums[i]<nums.length){
            for(let j=i;j<=i+nums[i];j++){
            if(dp[j]==0&&j!=0){
                dp[j]=dp[i]+1
            }
            }
        }
        else{
            return dp[i]+1
        }
        if(dp[nums.length-1]!=0)
            return dp[nums.length-1]
    } 
    return dp[nums.length-1]
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let length=nums.length
    let end=0
    let maxP=0
    let steps=0
    for(let i=0;i<length-1;i++){
        maxP=Math.max(maxP,i+nums[i])
        if(i==end){
        end=maxP
        steps++
        }

        }
    return steps
};

买卖股票的最佳时机

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