动态规划2——线性动态规划问题

前言：本文为学习力扣文章《动态规划精讲（一）》时的学习笔记，本文对其进行线性动态规划相关的文章和问题进行了一定的转载和修改并在其中加入了一些个人的理解。

线性动态规划简介

线性动态规划主要是从0开始从小到大依次递推过去的，特点为问题规模依次从0到i依次递增，较大规模的问题依赖较小规模问题的解

这里问题规模为 i 的含义是考虑前 i 个元素 [0…i] 时问题的解。

状态定义：

dp[n] := [0..n] 上问题的解

状态转移：

dp[n] = f(dp[n-1], ..., dp[0])

单串

单串是线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0…i]上，原问题的解，其中 i 位置的处理，根据不同的问题，主要有两种方式：

• 第一种是 i 位置必须取，此时状态可以进一步描述为 dp[i] := 考虑[0…i]上，且取 i，原问题的解；
• 第二种是 i 位置可以取可以不取

1. 依赖比 i 小的 O(1) 个子问题

53. 最大子数组和

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

一个数组有很多个子数组，求哪个子数组的和最大。可以按照子数组的最后一个元素来分子问题，确定子问题后设计状态

状态的推导是按照 i 从 0 到 n - 1 按顺序推的，推到 dp[i]，时，dp[i - 1], …, dp[0] 已经计算完。因为子数组是连续的，所以子问题 dp[i] 其实只与子问题 dp[i - 1] 有关。如果 [0…i-1] 上以 nums[i-1] 结尾的最大子数组和(缓存在 dp[i-1] )为非负数，则以 nums[i] 结尾的最大子数组和就在 dp[i-1] 的基础上加上 nums[i] 就是 dp[i] 的结果否则以 i 结尾的子数组就不要 i-1 及之前的数，因为选了的话子数组的和只会更小。

按照以上的分析，状态的转移可以写出来，如下

dp[i] = nums[i] + max(dp[i - 1], 0)

2. 依赖比 i 小的 O(n) 个子问题

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入是一个单串，首先思考单串问题中设计状态 dp[i] 时拆分子问题的方式：枚举子串或子序列的结尾元素来拆分子问题，设计状态 dp[i] := 在子数组 [0…i] 上，且选了 nums[i] 时，的最长上升子序列。

因为子序列需要上升，因此以 i 结尾的子序列中，nums[i] 之前的数字一定要比 nums[i] 小才行，因此目标就是先找到以此前比 nums[i] 小的各个元素，然后每个所选元素对应一个以它们结尾的最长子序列，从这些子序列中选择最长的，其长度加 1 就是当前的问题的结果。如果此前没有比 nums[i] 小的数字，则当前问题的结果就是 1 。

按照以上的分析，状态的转移方程可以写出来，如下

$$dp[i] = max_{j}(dp[j]) + 1$$

其中 $0 \leq j < i, nums[j] < nums[i]$。

单串问题：最经典单串LIS系列

1.最长上升子序列

给你一个整数数组 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

提示：

1 <= nums.length <= 2500
$-10^4 \leq nums[i] \leq 10^4$

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路