动态规划

常见的类型

• 动规基础：斐波那契数列 爬楼梯
• 背包问题（大厂考试最喜欢的考的类型之一）
• 打家劫舍
• 股票问题(例如哪天买，哪天卖赚的最多)
• 子序列问题

动规的误区

动态规划一般比较难，如果看了题解的话，可能会陷入背题解的死区，光看题解，照抄公式是没有用的，这次抄了题解，下次遇见了还是不会

dp数组含义

“dp” 数组是动态规划 (Dynamic Programming, DP) 的简称。动态规划是一种算法设计技巧，用于解决最优化问题。它的基本思想是将原问题分解为若干个子问题，再将子问题的解存储起来，供后续使用。这样可以避免重复计算，提高算法的效率。

“dp” 数组通常用于存储动态规划中的状态和结果。每个状态对应数组的一个元素，每个状态的转移由数组的元素之间的关系来实现。例如，在最长公共子序列 (Longest Common Subsequence, LCS) 问题中，dp 数组可能用于存储两个字符串的 LCS 的长度。

dp数组如何初始化

dp数组会进行初始化，但具体情况还是要根据具体的题目来定，比如有些题目是初始化为0，有些是从第i个才开始初始化为0，后续根据题目的要求来具体分析

dp遍历顺序

01背包问题里，需要两层的for循环，一层是背包，一层是物品，并且是先遍历背包，先遍历物品，所以我们可以明白，dp的遍历顺序是非常重要的

面试官喜欢先问你一道简单的题，然后在此基础上进行变种，难度一点点的上来

打印dp数组

如果自己的代码始终无法通过，可以打印dp数组，看数值是否和自己想象中的一样

斐波那契数

力扣题目链接

在做动态规划题目的时候，都需要定义一个一维或者是二维的用来做状态转移的数组，通常我们定义为dp

1.在该题中，dp[i]表示第i个斐波那契数的值

2.我们需要确定递推公式，之所以这道题是简单题便是因为这里的公式是直接告诉了我们：dp[i]=dp[i-1]+dp[i-2]

注意，这里虽然可以使用递归方式来解答，但会很繁琐：

递归法：

• 原理： 把 f(n) 问题的计算拆分成 f(n−1)和 f(n−2) 两个子问题的计算，并递归，以 f(0) 和 f(1)为终止条件。
• 缺点： 大量重复的递归计算，例如 f(n)和 f(n−1) 两者向下递归需要 各自计算 f(n−2) 的值。

3.dp数组初始化：dp[0]=0,dp[1]=1

4.确定遍历顺序：这道题就是很简单的从前往后进行遍历

5.打印数组

代码演示如下：

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    //处理特殊情况
    if(n==0||n==1) return n
    //dp数组初始化
    var dp=[0,1]
    for(let i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]//确定递推公式
        dp[i]=dp[i]%1000000007
    }
    return dp[n]
};

青蛙跳台阶

链接地址：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

这类求有多少种可能性的题目一般都有递推性质，即可f(n) 和 f(n−1)…f(1)之间是有联系的。

根据动态规划五部曲的解法来说：

1.在该题当中，dp[i]为台阶跳法

2.根据题意确定dp递推公式：dp[n]=dp[n-1]+dp[n-2]

n-1个台阶有f(n-1)种跳法，最后还剩一个台阶，最后青蛙只能最后一跳
n-2个台阶有f(n-2)种跳法，最后剩余二个台阶，有两种跳法：
       ①一次跳两个台阶
       ②一次跳一个台阶  但是这种跳法其实已经在n-1个台阶里包含了，所以
 f(n)=f(n-1)+f(n-2)

3.dp数组初始化：dp[0]=1,dp[1]=1

4.确认遍历顺序，和斐波那契数列一样，从前往后遍历即可

代码演示如下：

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    if(n==0||n===1) return 1//特殊情况处理
    let dp=[1,1]
    for(let i=2;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2])%1000000007//递推公式确定
    }
    return dp[n]
};

连续子数组的最大和

原题链接：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

1.该题的dp[i]显而易见为以num[i]结尾的连续子数组的最大值

2.该题的递推公式为：

• dp[i-1]>0,dp[i]=dp[i-1]+nums[i]
• dp[i-1]<=0,dp[i]=nums[i]

3.dp初始化为dp[0]=num[0]

最后输出的话为max(dp)

代码演示：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let dp=[nums[0]]//初始化dp数组
    for(let i=1;i<nums.length;i++){
        if(dp[i-1]>0) dp[i]=dp[i-1]+nums[i]
        else{
            dp[i]=nums[i]
        }
    }
    return Math.max(...dp)
};

股票买卖的最佳时机

原题链接

最容易想到的是暴力枚举，两层for循环进行枚举，找到最佳时机的解；还有一个贪心的思路，取左边的最小值，再取一个右边的最小值，也能得出最大的利润是多少

1.dp数组在这里有两个状态，一个是买，一个是卖；这个时候如果还用一维数组的话就不行，这时候就需要去定义一个二维dp数组,dp[i] [0]为持有该股票的最大现金，dp[i] [1]为不持有该股票的最大现金；最后需要在dp[n-1] [0]和dp[n-1] [1]当中选出一个最大值

2.dp递推公式：dp[i] [0] = max(dp[i - 1] [0], -prices[i])

3.dp数组初始化：dp[0] = [-prices[0], 0]

代码演示如下：

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const len = prices.length;
    if(len==0) return 0
    // 创建dp数组
    const dp = new Array(len).fill([0, 0]);
    // dp数组初始化
    dp[0] = [-prices[0], 0];
    for (let i = 1; i < len; i++) {
        // 更新dp[i]
        dp[i] = [
            Math.max(dp[i - 1][0], -prices[i]),
            Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]),
        ];
    }
    return dp[len - 1][1];
};