线性 DP
一维动态规划是最简单的，但是可以借此了解动态规划的思考方法与注意事项。 一维 DP 数组的定义方法也可以推广到更高维上去，作为高维 DP 数组的其中一维。
子数组问题
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：
输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
示例 4：
输入：nums = [-1,2]
输出：1
示例 5：
输入：nums = [1,2,3,5,-6,4,0,10]
输出：4
提示：
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
首先不看题目，看数组长度，N = 10^5，对于这个规模的数据，O(N^2) 的算法可能会超时，
这题和树、二分什么的也没有关系，考虑是不是一个 O(N) 的算法。
明显感觉是动态规划问题，注意状态是怎么转换的：
- 正数乘正数还是正数，乘负数变成负数；
- 负数乘正数还是负数，乘负数变成正数。
假如设 dp[i] 是以 nums[i] 结尾，乘积为正的最长子数组的长度。那么因为 dp[i+1] 不仅仅与 dp[i] 有关，
还可能由负数乘负数转化而来，这个设计不合理。
所以设 positive[i] 是以 nums[i] 结尾，乘积为正的最长子数组的长度，
又设 negative[i] 是以 nums[i] 结尾，乘积为负的最长子数组的长度。
列写正式的状态转换式：
if (nums[i] > 0):
positive[i] = positive[i-1] + 1
negative[i] = negative[i-1] + 1
if (nums[i] < 0):
positive[i] = negative[i-1] + 1
negative[i] = positive[i-1] + 1
除状态转换式外还需要的是初始状态，这个简单，单独判断一下就好了：
positive[0] = nums[0] > 0 ? 1 : 0
negative[0] = nums[0] < 0 ? 1 : 0
但是先别急着写代码，有了思路之后的第一件事应该是代入用例验证一下，以防设计出错，写了半天白忙活。
看了用例一下就发现了，还有 nums[i] == 0 的情况没有考虑。
以 nums[i] 结尾，乘积为正或负的最长子数组的长度显然都是零了。那么：
if (nums[i] == 0):
positive[i] = 0
negative[i] = 0
再看一下示例 2，发现不对劲：
nums 0 1 -2 -3 -4
positive 0 1 2 3 4
negative 0 1 2 3 4
expected: 3 found: 4
原因在于 nums[0] == 0 重置了状态，其后的 positive[1]、negative[1] 需要像初始状态一样考虑。
换句话说，当 negative[i-1] == 0，nums[i] 为正数时 negative[i] 还是 0，为负数时也没有
负负得正的效果，positive[i] 不等于 negative[i-1] + 1。
综上，修正状态转换式：
if (nums[i] > 0):
positive[i] = positive[i-1] + 1
negative[i] = negative[i-1] == 0 ? 0 : negative[i-1] + 1
if (nums[i] < 0):
positive[i] = negative[i-1] == 0 ? 0 : negative[i-1] + 1
negative[i] = positive[i-1] + 1
同时注意，这里也包含了初始状态，不需要再单独考虑。
最后注意，状态 i 仅仅与状态 i-1 有关，所以可以对这个一维线性动态规划进行状态压缩，仅用迭代 变量 positive, negative 代替动态规划的数组。
class Solution {
public int getMaxLen(int[] nums) {
int positive = 0, negative = 0;
int res = 0;
for (final int num : nums) {
if (num == 0) {
positive = 0;
negative = 0;
} else if (num > 0) {
positive++;
negative = negative == 0 ? 0 : negative + 1;
} else {
int lastNegative = negative;
negative = positive + 1;
positive = lastNegative == 0 ? 0 : lastNegative + 1;
}
res = Math.max(res, positive);
}
return res;
}
}
子序列问题
子数组是一个数组的非空连续子集，而子序列则不要求连续。显然，涉及子序列的动态规划题目一般要更难一些， 重点在于 DP 数组的意义要如何规定。例如最长上升子序列（LIS）问题：
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
定义
dp[i]为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度。dp[i] = max(dp[j]) + 1, 其中
0≤j<i且num[j]<num[i]
之所以要求 nums[i] 必须被选取是为了能在状态转移方程中判断当前元素能否添加
到前面的 LIS 后面（即是否满足条件 num[j]<num[i]），换句话说， LIS 的最后一个元素就是
这个 LIS 的抓手。
但是子序列问题的动态规划求解不总是以“以第 i 个元素结尾的序列”作为一维。例如 115.不同的子序列：
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
示例 1：
输入：S = "rabbbit", T = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2：
输入：S = "babgbag", T = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
dp[i][j] 代表 S 前 j 个字符的子序列中 T 前 i 个字符构成的子串的出现次数
当 S[j] == T[i] , dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
当 S[j] != T[i] , dp[i][j] = dp[i][j-1]
原因就在于子序列的后一个元素与前一个元素没有什么约束关系。
背包 DP
背包问题一般这样描述：有 N 种物品和一个容量为 V 的背包。第 i 种物品的费用是 c[i]，
价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。如果每种物品仅有一件，可选择放或不放，那么
就是 0-1 背包问题；如果每种物品都有无限件可用，那么就是完全背包问题。
先考虑每种物品仅有一件的情况。
一般这样定义状态：dp[i][v] 表示前 i 种物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是：
dp[i][v] = f{dp[i-1][v],dp[i-1][v-c[i]]+w[i]} // f 函数在这里是 max
“将前 i 种物品放入容量为 v 的背包中”这个子问题，若只考虑第 i 种物品的策略（放或不放），
那么就可以转化为一个只牵扯前 i-1 种物品的问题。如果不放第 i 种物品，
那么问题就转化为“前 i-1 种物品放入容量为 v 的背包中”，价值为 dp[i-1][v]；如果放第 i 种物品，
那么问题就转化为“前 i-1 种物品放入剩下的容量为 v-c[i] 的背包中”，
此时能获得的最大价值就是 dp[i-1][v-c[i]] 再加上通过放入第 i 种物品获得的价值 w[i]。
注意状态转移方程中计算 dp[i][v] 时只使用到了上一层正上方（dp[i-1][v]）和左边（dp[i-1][v-c[i]]）的状态，
因此我们可以在实现时压缩状态数组：
for i=1..N
for v=V..0
if v>=c[i]
dp[v]=f{dp[v],dp[v-c[i]]+w[i]}
else
dp[v]=f{dp[v]}
注意内部循环从 V 到 0 进行，这样保证了 dp[v-c[i]] 访问的是上一层的状态。
v < c[i] 时当前状态只可能从上一层正上方迁移而来，在压缩状态数组的实现中刚好什么都不需要做，
因此我们事实上这样写代码：
for i=1..N
for v=V..c[i] // 逆序
dp[v]=f{dp[v],dp[v-c[i]]+w[i]}
接下来考虑每种物品有无限件的情况。那么状态转移方程就变成：
dp[i][v] = f{dp[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v}
事实上，它等价于：
dp[i][v] = f{dp[i-1][v],dp[i][v-c[i]]+w[i]}
注意这里状态转移方程中计算 dp[i][v] 时使用到了上一层正上方（dp[i-1][v]）和当前层左边（dp[i][v-c[i]]）的状态，
因此我们用压缩状态数组实现时内部循环应当改为顺序（从 c[i] 到 V）以保证 dp[v-c[i]] 访问的是当前层的状态：
for i=1..N
for v=c[i]..V // 顺序
dp[v]=f{dp[v],dp[v-c[i]]+w[i]}
这样计算的结果中，选择的物品是无序的，即方案 [1,1,3] 与方案 [3,1,1] 被认为是同一种。
如果碰到了 377.组合总和 Ⅳ 这样的题目，
要求区分组合 (1,1,3) 与 (3,1,1) 等，需要修改状态转移方程为：
dp[i][v] = f{dp[i-1][v],dp[N][v-c[i]]+w[i]} // f 函数在这里是 sum
因为其中的 dp[N][v-c[i]] 表示“将所有种类物品放入容量为 v-c[i] 的背包中的组合数”。
下面讨论实现：因为 dp[i][v] 用到了左下角的值，所以 dp 矩阵扫描方式改为外层按列扫描。
for v=1..V // 内外循环调换顺序
for i=1..N
if v>=c[i]
dp[v]=f{dp[v],dp[v-c[i]]+w[i]} // 不是矩阵转置，dp 索引还是 v
else
dp[v]=f{dp[v]}
实际的问题当然不会描述得这么明显，所以需要能根据特征识别背包问题或把问题转化为背包问题。
背包问题的特征是一系列的可选择元素（DP 的层数）、给定的有限数的约束条件（如物品总重量 W、元素的加和 S，
作为 DP 矩阵的列）和代求的不定的量（如是否有可行方案、可行方案数目、元素的加和的最值，作为 dp[i][j] 的值）。
有时候还需要根据方程关系进行等价变形以得到背包问题，比如下面这个问题：
// 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
// 对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
// 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
// 示例：
// 输入：nums: [1, 1, 1, 1, 1], S: 3
// 输出：5
// 解释：
// -1+1+1+1+1 = 3
// +1-1+1+1+1 = 3
// +1+1-1+1+1 = 3
// +1+1+1-1+1 = 3
// +1+1+1+1-1 = 3
// 一共有5种方法让最终目标和为3。
//
// 提示：
// 数组非空，且长度不会超过 20 。
// 初始的数组的和不会超过 1000 。
// 保证返回的最终结果能被 32 位整数存下。
// 此问题可以转化为子集划分问题
//
// 将一个集合划分成两个子集 A,B, 问满足 sum(A) - sum(B) = Target的分法有多少种
// 两端同时加上集合元素和 sum,得到 2 * sum(A) = Target + sum ==> sum(A) = (Target + sum) / 2
//
// 又已知 sum(A) = sum(B) + Target >= Target, sum = sum(A) + sum(B) >= sum(A)
// 故得预筛选条件 sum >= Target 和 (Target + sum) % 2 == 0
import java.util.Arrays;
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = Arrays.stream(nums).sum();
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
int[] dp = new int[sum + 1];
dp[0] = 1; // 0 元素加和为 0 有 1 种方案
for (int num : nums) {
for (int j = dp.length - 1; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[(sum + S) / 2];
}
}
最后总结一下模板：
dp[i][v] = f{dp[i-1][v],dp[
i-1][v-c[i]]+w[i]} // 0-1 背包dp[i][v] = f{dp[i-1][v],dp[
i][v-c[i]]+w[i]} // 完全背包dp[i][v] = f{dp[i-1][v],dp[
N][v-c[i]]+w[i]} // 考虑物品顺序的完全背包
对于其中的 f 函数：
- 在“方案是否存在”问题中，
f = or(布尔或) - 在“方案有多少种”问题中，
f = sum - 在“最优方案”问题中，
f = best(比如 max 或者 min)
至于具体实现中的扫描方式，根据状态转移方程很容易想出来，初始条件一般也不难，都不需要记忆。
DP 数组的维度
动态规划的核心难点在于 DP 数组的定义与状态转移方程的寻找，而后者又直接依赖于前者。 而 DP 数组的定义问题分解一下就是要确定数组的各个维度分别代表什么。
一般地，字符串问题常取“前 i 个字符”，“子串 [i, j)”，“s1 的前 i 个字符和 s2 的前 j 个字符”等。
比较特别的有把状态枚举出来作为一维，
以 123.买卖股票的最佳时机 III 为例：
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
//
// 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
//
// 示例 1:
// 输入: [3,3,5,0,0,3,1,4]
// 输出: 6
// 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
// 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
//
// 示例 2:
// 输入: [1,2,3,4,5]
// 输出: 4
// 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
// 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
// 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
//
// 示例 3:
// 输入: [7,6,4,3,1]
// 输出: 0
// 解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
object Solution {
def maxProfit(prices: Array[Int]): Int = {
// 状态：0:未交易; 1:买入一次; 2:卖出1次; 3:买入2次; 4:卖出2次
val dp = Array(0, -prices(0), Int.MinValue/2, Int.MinValue/2, Int.MinValue/2) // 由二维数组压缩而来
for {
i <- 1 until prices.length
} {
dp(4) = dp(4) max dp(3) + prices(i)
dp(3) = dp(3) max dp(2) - prices(i)
dp(2) = dp(2) max dp(1) + prices(i)
dp(1) = dp(1) max dp(0) - prices(i)
// dp(0) = dp(0) // dp(0) 可以用常数 0 代替
}
dp.max
}
}
最后附上 GitHub：https://github.com/gonearewe
