标签：遍历 nums 示例 TS JS --- 数组序列 dp

一、动态规划

动态规划（dynamic programming, DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。

注意，动态规划和分而治之是不同的方法。分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则是将问题分解成相互依赖的子问题。

用动态规划解决问题时，要遵循三个重要步骤：

定义子问题；
实现要反复执行来解决子问题的部分（这一步要参考前一节讨论的递归的步骤）；
识别并求解出基线条件。

能用动态规划解决的一些著名问题如下。

背包问题：给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。
最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余下元素的顺序而得到）。
矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序。
硬币找零：给出面额为d1, …, dn的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。
图的全源最短路径：对所有顶点对(u, v)，找出从顶点u到顶点v的最短路径。通常使用Floyd-Warshall算法

动态规划和贪心的区别

如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的。所以动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的，这⼀点就区分于贪⼼，贪⼼没有状态推导，⽽是从局部直接选最优的

我举了⼀个背包问题的例⼦。例如：有N件物品和⼀个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。但如果是贪⼼呢，每次拿物品选⼀个最⼤的或者最⼩的就完事了，和上⼀个状态没有关系。所以贪⼼解决不了动态规划的问题。

重点

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。对于动态规划问题，我将拆解为如下五步曲

dp数组以及其下标的含义 dp[i][j]、dp[i]
递推公式
dp数组如何初始化
遍历顺序
打印dp数组

leetcode题精选

入门------dp仅一维数组

[509] 斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

这⾥我们要⽤⼀个⼀维dp数组来保存递归的结果

确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

确定递推公式为什么这是⼀道⾮常简单的⼊⻔题⽬呢？

因为题⽬已经把递推公式直接给我们了：状态转移⽅程 dp[i] = dp[i - 1] + dp[i - 2];
dp数组如何初始化

题⽬中把如何初始化也直接给我们了，如下：

dp[0] = 0;

dp[1] = 1;

确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序⼀定是从前到后遍历的
举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导⼀下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是⼀致的

function fib(n: number): number {
    if(n<=1) return n;
    const dp:number[]= [];
    //初始化dp数组
    dp[0] = 0;
    dp[1] = 1;
    //从前向后遍历
    for(let i=2;i<=n;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }   
    return dp[n] 
};

时间：O(n) 空间：O(n)

function fib(n: number): number {
    if(n<=1) return n;
    const dp:number[]= [];
    //初始化dp数组
    dp[0] = 0;
    dp[1] = 1;
    //从前向后遍历
    for(let i=2;i<=n;i++){
        let sum = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = sum
    }   
    return dp[1] 
};

[70] 爬楼梯

爬到第⼀层楼梯有⼀种⽅法，爬到⼆层楼梯有两种⽅法。

那么第⼀层楼梯再跨两步就到第三层，第⼆层楼梯再跨⼀步就到第三层。

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

我们来分析⼀下，

动规五部曲：

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

确定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数组）应该是这样

1	2	3	5	8

function climbStairs(n: number): number {
    if(n<=1) return n;
    const dp:number[] = [];
    dp[1] = 1;
    dp[2] = 2;
    for(let i=3 ;i<=n;i++){
        let sum = dp[1] + dp[2];
        dp[1] = dp[2];
        dp[2] = sum;
    }
    return dp[2]
};

[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 。

确定dp数组以及下标的含义

dp[i]： i代表房屋的索引，dp[i]代表偷窃最大值
确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房⼀定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的⾦额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这⾥是考虑，并不是⼀定要偷i-1房，这是很多同学容易混淆的点）然后dp[i]取最⼤值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]。
```
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
```
确定遍历顺序从递推公式遍历顺序⼀定是从前向后遍历的
举例推导dp数组

//空间O(n)
function rob(nums: number[]): number {

    if(!nums) return 0;
    const dp:number[] = [];

    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);

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

};

//空间O(1)

[213] 打家劫舍II

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

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

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：

输入：nums = [1,2,3]
输出：3

对于一个数组，成环的话主要有如下三种情况：

情况一：考虑不包含首尾元素

情况二：考虑包含首元素，不包含尾元素

情况三：考虑包含尾元素，不包含首元素

注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！对于情况三，取nums[1] 和 nums[3]就是最大的。

而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

分析到这里，本题其实比较简单了。剩下的和198.打家劫舍就是一样的了。

function rob(nums: number[]): number {

    if(!nums) return 0;
    if(nums.length===1) return nums[0];
    //不包括首元素
    const res1 = robRange(nums,1,nums.length-1);
    //不包括尾元素
    const res2 = robRange(nums,0,nums.length-2);
    return Math.max(res1,res2);

};

function robRange(nums:number[],start:number,end:number):number{
    if(!nums) return 0;
    if(start==end) return nums[start];
    // const dp:number[] = [];
    const dp = new Array(nums.length).fill(0);
    dp[start] = nums[start];
    dp[start+1] = Math.max(nums[start],nums[start+1]);
    for(let i=start+2; i<=end; i++){
        dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
    }
    return dp[end];
}

打家劫舍III是关于树形dp的，先不讲

0-1背包/完全背包

直接看代码随想录讲解

0-1背包问题，你该了解这些！ (qq.com)

01背包

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

问背包能背的物品最大价值是多少？

以下讲解和图示中出现的数字都是以这个例子为例。

二维dp数组01背包

依然动规五部曲分析一波。

确定dp数组以及下标的含义

对于背包问题，有一种写法，是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

只看这个二维数组的定义，大家一定会有点懵，看下面这个图：

要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。

确定递推公式

再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp[i][j]，

由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

首先从dp[i][j]的定义触发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：

再看其他情况。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

代码如下：

// 倒叙遍历
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i为0时候的情况
}

大家应该发现，这个初始化为什么是倒叙的遍历的？正序遍历就不行么？

正序遍历还真就不行，dp[0][j]表示容量为j的背包存放物品0时候的最大价值，物品0的价值就是15，因为题目中说了每个物品只有一个！所以dp[0][j]如果不是初始值的话，就应该都是物品0的价值，也就是15。

但如果一旦正序遍历了，那么物品0就会被重复加入多次！例如代码如下：

// 正序遍历
for (int j = weight[0]; j <= bagWeight; j++) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

例如dp[0][1] 是15，到了dp[0][2] = dp[0][2 - 1] + 15; 也就是dp[0][2] = 30 了，那么就是物品0被重复放入了。

所以一定要倒叙遍历，保证物品0只被放入一次！这一点对01背包很重要，后面在讲解滚动数组的时候，还会用到倒叙遍历来保证物品使用一次！

此时dp数组初始化情况如图所示：

dp[0][j] 和 dp[i][0] 都已经初始化了，那么其他下标应该初始化多少呢？

dp[i][j]在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，因为0就是最小的了，不会影响取最大价值的结果。

如果题目给的价值有负数，那么非0下标就要初始化为负无穷了。例如：一个物品的价值是-2，但对应的位置依然初始化为0，那么取最大值的时候，就会取0而不是-2了，所以要初始化为负无穷。

这样才能让dp数组在递归公式的过程中取最大的价值，而不是被初始值覆盖了。

最后初始化代码如下：

// 初始化 dp
vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = bagWeight; j >= weight[0]; j--) {
    dp[0][j] = dp[0][j - weight[0]] + value[0];
}

费了这么大的功夫，才把如何初始化讲清楚，相信不少同学平时初始化dp数组是凭感觉来的，但有时候感觉是不靠谱的。

确定遍历顺序

在如下图中，可以看出，有两个遍历的维度：物品与背包重量

那么问题来了，先遍历物品还是先遍历背包重量呢？

其实都可以！！但是先遍历物品更好理解。

那么我先给出先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 这个是为了展现dp数组里元素的变化
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        
    }
}

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）

例如这样：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

为什么也是可以的呢？

要理解递归的本质和递推的方向。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。

dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向（包括正左和正上两个方向），那么先遍历物品，再遍历背包的过程如图所示：

再来看看先遍历背包，再遍历物品呢，如图：

大家可以看出，虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，根本不影响dp[i][j]公式的推导！

但先遍历物品再遍历背包这个顺序更好理解。

其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。

举例推导dp数组

来看一下对应的dp数组的数值，如图：

最终结果就是dp[2][4]。

建议大家此时自己在纸上推导一遍，看看dp数组里每一个数值是不是这样的。

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

很多同学做dp题目，遇到各种问题，然后凭感觉东改改西改改，怎么改都不对，或者稀里糊涂就改过了。

主要就是自己没有动手推导一下dp数组的演变过程，如果推导明白了，代码写出来就算有问题，只要把dp数组打印出来，对比一下和自己推导的有什么差异，很快就可以发现问题了。

完整测试代码

void test_2_wei_bag_problem1() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 二维数组
    vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));

    // 初始化 
    for (int j = bagWeight; j >= weight[0]; j--) {
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }

    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

        }
    }

    cout << dp[weight.size() - 1][bagWeight] << endl;
}

int main() {
    test_2_wei_bag_problem1();
}

以上遍历的过程也可以这么写：

// 遍历过程
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        if (j - weight[i] >= 0) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
}

这么写打印出来的dp数据这就是这样：

空出来的0其实是用不上的，版本一能把完整的dp数组打印出来，出来我用版本一来讲解。

钱币找零---完全背包问题

[322] 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

[518] 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：

输入：amount = 10, coins = [10]
输出：1

子串和子序列

子序列（不连续）
- 300.最长上升子序列
- 1143.最长公共子序列
- 1035.不相交的线
子序列（连续）
- 674.最长连续递增序列
- 718.最长重复子数组
- 53.最大子序和
编辑距离
- 392.判断子序列
- 115.不同的子序列
- 583.两个字符串的删除操作
- 72.编辑距离
回文
- 647.回文子串
- 516.最长回文子序列

[300] 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

dp[i]的定义

dp[i]表示i之前包括i的最⻓上升⼦序列。
状态转移⽅程

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这⾥不是要dp[i] 与 dp[j] + 1进⾏⽐较，⽽是我们要取dp[j] + 1的最⼤值。
dp[i]的初始化

dp[i] 每一个i 都是1
确定遍历顺序

dp[i] 是有0到i-1各个位置的最⻓升序⼦序列推导⽽来，那么遍历i⼀定是从前向后遍历。 j其实就是0到i-1，遍历i的循环⾥外层，遍历j则在内层，代码如下
```
for (int i = 1; i < nums.size(); i++) {
 for (int j = 0; j < i; j++) {
 if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
 }
 if (dp[i] > result) result = dp[i]; // 取⻓的⼦序列
}
```
举例推导dp数组

一维全0 数组：new Array(m).fill(0)

function lengthOfLIS(nums: number[]): number {

    if (nums.length <= 1) return nums.length;
    let dp = new Array(nums.length).fill(1);
    let res = dp[0];
    for(let i=1 ;i<nums.length; i++){
        for(let j= 0; j<i; j++){
            if(nums[i]>nums[j]) {
            dp[i] = Math.max(dp[i],dp[j]+1) 
            res = Math.max(res,dp[i]);
            }
        }
    }
    return res
};

[674] 最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

function findLengthOfLCIS(nums: number[]): number {

    if(nums.length<=1) return nums.length;
    const dp:number[] = new Array(nums.length).fill(1);
    let res = 0;

    for(let i=0;i<nums.length-1;i++){
    
            if(nums[i+1]>nums[i])
            dp[i+1] = dp[i]+1;

        res = Math.max(dp[i+1],res); 
    }

    return res
};

贪心

[1143] 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

确定dp数组（dp table）以及下标的含义

dp[i][j]表示长度为[0,i-1] 和 [0,j-1] 的两个字符串的最长公共子序列长度设长度为length+1,从1处开始，更方便些
确定递推公式

比较text1[i-1]和text2[j-1]是否一样，如果一样,则为dp[i-1][j-1]+1

如果不一样则分别在text1和text2向后多取一位，取最大值，即Math.max(dp[i-1][j],dp[i-1][j])
确定初始化的值

dp[i][0]=0 dp[0][j]=0
确定遍历顺序

从前往后双层遍历
打印dp数组

根据状态表得出状态转移方程，当两个字符相同时，仍然是左上角的单元格加一，否则比较左和上两个单元格的值，取较大值。

dp[i][j] = (dp[i-1][j-1] + 1) | max(dp[i-1][j], dp[i][j-1])

二维全0数组定义：new Array(m).fill(0).map((x) => new Array(n).fill(0))

function findLengthOfLCIS(nums: number[]): number {

    if(nums.length<=1) return nums.length;
    const dp:number[] = new Array(nums.length).fill(1);
    let res = 0;

    for(let i=0;i<nums.length-1;i++){
    
            if(nums[i+1]>nums[i])
            dp[i+1] = dp[i]+1;

        res = Math.max(dp[i+1],res); 
    }

    return res
    
};

[718] 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

确定dp数组（dp table）以及下标的含义

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最⻓重复⼦数组⻓度为dp[i][j]。

此时细⼼的同学应该发现，那dp[0][0]是什么含义呢？总不能是以下标-1为结尾的A数组吧。其实dp[i][j]的定义也就决定着，我们在遍历dp[i][j]的时候i 和 j都要从1开始。那有同学问了，我就定义dp[i][j]为以下标i为结尾的A，和以下标j 为结尾的B，最⻓重复⼦数组⻓度。不⾏么？⾏倒是⾏！但实现起来就麻烦⼀点，⼤家看下⾯的dp数组状态图就明⽩了。
确定递推公式

根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1; 根据递推公式可以看出，遍历i 和 j 要从1开始
确定初始化的值

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！但dp[i][0] 和dp[0][j]要初始值，因为为了⽅便递归公式dp[i][j] = dp[i - 1][j - 1] + 1; 所以dp[i][0] 和dp[0][j]初始化为0。举个例⼦A[0]如果和B[0]相同的话，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，正好符合递推公式逐步累加起来。
确定遍历顺序

外层for循环遍历A，内层for循环遍历B。那⼜有同学问了，外层for循环遍历B，内层for循环遍历A。不⾏么？也⾏，⼀样的，我这⾥就⽤外层for循环遍历A，内层for循环遍历B了。
打印dp数组

//注意使用==或===
function findLength(nums1: number[], nums2: number[]): number {

    const dp:number[][] = new Array(nums1.length+1).fill(0).map(x=>new Array(nums2.length+1).fill(0));
    let res = 0;
    for(let i=1; i<=nums1.length; i++){
        for(let j=1; j<=nums2.length; j++){
            if(nums1[i-1]==nums2[j-1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            res = Math.max(res,dp[i][j]);    
        }
    }
    return res;
};

另一种解法 ------ 滚动数组

[53] 最大子数组和

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

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

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

确定dp数组（dp table）以及下标的含义

dp[i]：包括下标i之前的最⼤连续⼦序列和为dp[i]。
确定递推公式

dp[i]只有两个⽅向可以推出来：

dp[i - 1] + nums[i]，即：nums[i]加⼊当前连续⼦序列和

nums[i]，即：从头开始计算当前连续⼦序列和

⼀定是取最⼤的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
确定初始化的值

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。

dp[0]应该是多少呢?

更具dp[i]的定义，很明显dp[0]因为为nums[0]即dp[0] = nums[0]。
确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
打印dp数组

function maxSubArray(nums: number[]): number {
    if(!nums) return 0;
    const dp:number[] = new Array(nums.length).fill(0);
    let res = nums[0];
    dp[0] = nums[0];
    for(let i=1; i<nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i])
            res = Math.max(dp[i],res);
    }
    return res;
};

[392] 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

这道题应该算是编辑距离的⼊⻔题⽬，因为从题意中我们也可以发现，只需要计算删除的情况，不⽤考虑增加和替换的情况。所以掌握本题也是对后⾯要讲解的编辑距离的题⽬打下基础。

确定dp数组（dp table）以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。

有同学问了，为啥要表示下标i-1为结尾的字符串呢，为啥不表示下标i为结尾的字符串呢？

用i来表示也可以！

但我统一以下标i-1为结尾的字符串来计算，这样在下面的递归公式中会容易理解一些，如果还有疑惑，可以继续往下看。

确定递推公式

在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
- 相当于t要删除元素，继续匹配

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1（如果不理解，在回看一下dp[i][j]的定义）

if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1];

dp数组如何初始化

从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。

这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：

如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。

这里dp[i][0]和dp[0][j]是没有含义的，仅仅是为了给递推公式做前期铺垫，所以初始化为0。

确定遍历顺序

同理从从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右

如图所示：

举例推导dp数组

以示例一为例，输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：

dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。

图中dp[s.size()][t.size()] = 3，而s.size() 也为3。所以s是t 的子序列，返回true

function isSubsequence(s: string, t: string): boolean {
    // if(!s) return false;
    const dp:number[][] = new Array(s.length+1).fill(0).map(x=>new Array(t.length+1).fill(0));
    for(let i=1; i<=s.length; i++){
        for(let j=1; j<=t.length; j++){
            if(s[i-1]==t[j-1]){
                //如果相同+1
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                //不同的话向前找
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[s.length][t.length]==s.length?true:false;

};

[72] 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

确定dp数组（dp table）以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，转换最少操作数。

确定递推公式

if (word1[i - 1] == word2[j - 1])
- 不操作
if (word1[i - 1] != word2[j - 1])
- 增
- 删
- 换

也就是如上四种情况。

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1] 就是 dp[i][j]了。

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

操作一：word1增加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-2为结尾的word1 与 i-1为结尾的word2的最近编辑距离加上一个增加元素的操作。

即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2添加一个元素，使其word1[i - 1]与word2[j - 1]相同，那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离加上一个增加元素的操作。

即 dp[i][j] = dp[i][j - 1] + 1;

这里有同学发现了，怎么都是添加元素，删除元素去哪了。

word2添加一个元素，相当于word1删除一个元素，例如 word1 = "ad" ，word2 = "a"，word2添加一个元素d，也就是相当于word1删除一个元素d，操作数是一样！

操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离加上一个替换元素的操作。

即 dp[i][j] = dp[i - 1][j - 1] + 1;

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

递归公式代码如下：

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];
}
else {
    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

dp数组如何初始化

dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对空字符串做添加元素的操作就可以了，即：dp[i][0] = i;

同理dp[0][j] = j;

for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

确定遍历顺序

从如下四个递推公式：

dp[i][j] = dp[i - 1][j - 1]
dp[i][j] = dp[i - 1][j - 1] + 1-----替换
dp[i][j] = dp[i][j - 1] + 1------减少
dp[i][j] = dp[i - 1][j] + 1------增加

可以看出dp[i][j]是依赖左方，上方和左上方元素的，如图：

所以在dp矩阵中一定是从左到右从上到下去遍历。

代码如下：

for (int i = 1; i <= word1.size(); i++) {
    for (int j = 1; j <= word2.size(); j++) {
        if (word1[i - 1] == word2[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1];
        }
        else {
            dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
        }
    }
}

举例推导dp数组

以示例1，输入：word1 = "horse", word2 = "ros"为例，dp矩阵状态图如下：

function minDistance(word1: string, word2: string): number {

    const dp:number[][] = new Array(word1.length+1).fill(0).map(x=>new Array(word2.length).fill(0));

    //初始化
    for (let i = 0; i <= word1.length; i++) dp[i][0] = i;
    for (let j = 0; j <= word2.length; j++) dp[0][j] = j;

    //遍历
    for (let i = 1; i <= word1.length; i++){
        for (let j = 1; j <= word2.length; j++){
            if(word1[i-1]==word2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
            }
        }
    }
    return dp[word1.length][word2.length]

};

[647] 回文子串---dp为布尔类型数组

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：输入的字符串长度不会超过 1000。

两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。

时间复杂度：O(n^3)

动规解法：

确定dp数组（dp table）以及下标的含义

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
情况二：下标i 与 j相差为1，例如aa，也是文子串
情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

以上三种情况分析完了，那么递归公式如下：

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

result就是统计回文子串的数量。

注意这里我没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i][j]初始化的时候，就初始为false。

dp数组如何初始化

dp[i][j]可以初始化为true么？当然不行，怎能刚开始就全都匹配上了。

所以dp[i][j]初始化为false。

确定遍历顺序

遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是先经过计算的。

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。

举例推导dp数组

举例，输入："aaa"，dp[i][j]状态如下：

图中有6个true，所以就是有6个回文子串。

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

function countSubstrings(s: string): number {

    if(!s) return 0;

    const dp:boolean[][] = new Array(s.length).fill(false).map(x=>new Array(s.length).fill(false));
    let res = 0;

    for(let i=s.length-1;i>=0;i--){
        for (let j = i; j < s.length; j++){
            if(s[i] == s[j]){
                  if (j - i <= 1) { // 情况一 和 情况二
                        res++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        res++;
                        dp[i][j] = true;
                    }
            }
        }
    }
    return res;


};

[516] 最长回文子序列---非连续的

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入："babad"

输出："bab"

注意："aba" 也是一个有效答案。

示例 2：

输入："cbbd"

输出："bb"

求最长回文子串，这是一道非常经典的字符串问题，需要重点理解。

确定dp数组（dp table）以及下标的含义

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

确定递推公式

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如图：

（如果这里看不懂，回忆一下dp[i][j]的定义）

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

代码如下：

if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}

dp数组如何初始化

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;

确定遍历顺序

从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出，dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j]，

也就是从矩阵的角度来说，dp[i][j] 下一行的数据。所以遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。

递推公式：dp[i][j] = dp[i + 1][j - 1] + 2，dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 分别对应着下图中的红色箭头方向，如图：

代码如下：

for (int i = s.size() - 1; i >= 0; i--) {
    for (int j = i + 1; j < s.size(); j++) {
        if (s[i] == s[j]) {
            dp[i][j] = dp[i + 1][j - 1] + 2;
        } else {
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
}

举例推导dp数组

输入s:"cbbd" 为例，dp数组状态如图：

红色框即：dp[0][s.size() - 1]; 为最终结果。

function longestPalindromeSubseq(s: string): number {
    if(!s) return 0;

    const dp:number[][] = new Array(s.length).fill(0).map(x=>new Array(s.length).fill(0));
    
    for (let  i = 0; i < s.length; i++)  dp[i][i] = 1;

    for(let i=s.length-1;i>=0;i--){
        for(let j=i+1;j<s.length;j++){
            if(s[i]==s[j]){
                dp[i][j] = dp[i+1][j-1] +2
            }else{
                dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j])
            }
        }
    }
    return dp[0][s.length-1]
};

股票

[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, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

[122] 买卖股票的最佳时机 II

其他

[42] 接雨水-------困难题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

单调栈+动态规划

二、贪心算法

贪心算法（Greedy Algorithm）会在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，不能回退，从而希望结果是最好或最优的算法。它是动态规划的一种特例，需要满足更多的限制条件。

贪心算法在有最优子结构的问题中尤为有效（例如求图的最小生成树、哈夫曼编码等），最优子结构是指局部最优解能决定全局最优解。即问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

比如Dijkstra算法、Prim算法和Kruskal算法都是贪心的问题

leetcode题精选

一、区间调度

给定多个 [start, end] 的区间集合，算出有多少个不重叠的区间。例如 [1,3], [2,4], [3,6]，有两个不重叠的区间 [1,3], [3,6]，因为边界相互接触，并不算重叠。

[435] 无重叠区间

解题思路如下所列：
（1）根据终点对区间进行排列。
（2）从区间集合中选取一个终点最小的区间 [start, minEnd]。
（3）将所有与 [start, minEnd] 相交的区间从集合中移除。
（4）重复执行（2）和（3），直至遍历完集合。
具体实现代码如下所示。

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let curEnd = intervals[0],          //终点最小的区间
    count = 1;                        //不重叠的区间数
  intervals.forEach((value) => {
    if (value[0] < curEnd[1]) {       //过滤起点比curEnd终点小的区间
      return;
    }
    count++;
    curEnd = value;
  });
  return count;
}

二、分糖果

[455] 分发饼干

三、钱币找零

[860] 柠檬水找零

四、股票

[122] 买卖股票的最佳时机 II

其他

[402] 移掉K位数字

[392] 判断子序列

[55] 跳跃游戏

标签：遍历,nums,示例,TS,JS,---,数组,序列,dp
From： https://www.cnblogs.com/guibi/p/16637239.html

JS/TS算法---dp和贪心

一、动态规划

leetcode题精选

入门------dp仅一维数组

[509] 斐波那契数

[70] 爬楼梯

[198] 打家劫舍

[213] 打家劫舍II

0-1背包/完全背包

01背包

二维dp数组01背包

完整测试代码

钱币找零---完全背包问题

[322] 零钱兑换

[518] 零钱兑换 II

子串和子序列

[300] 最长递增子序列

[674] 最长连续递增序列

[1143] 最长公共子序列

[718] 最长重复子数组

[53] 最大子数组和

[392] 判断子序列

[72] 编辑距离

[647] 回文子串---dp为布尔类型数组

[516] 最长回文子序列---非连续的

股票

[121] 买卖股票的最佳时机

[122] 买卖股票的最佳时机 II

其他

[42] 接雨水-------困难题

二、贪心算法

leetcode题精选

一、区间调度

[435] 无重叠区间

二、分糖果

[455] 分发饼干

三、钱币找零

[860] 柠檬水找零

四、股票

[122] 买卖股票的最佳时机 II

[122] 买卖股票的最佳时机 II

其他

[402] 移掉K位数字

[392] 判断子序列

[55] 跳跃游戏

相关文章

赞助商

阅读排行