算法【Java】—— 动态规划之子序列问题
最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence
状态表示：和之前的经验一样，dp[i] 表示 以 i 为结尾元素的所有递增子序列中最大长度是多少
状态转移方程推导：从 i 前面的元素开始寻找，当 nums[j] < nums[i] 的时候，则找到一个递增子序列，比较出最大长度，dp[i] = max(dp[i], dp[j] + 1)
初始化：由于一个元素就可以构成一个序列，所以将 dp 表所有元素初始化为 1
填表顺序：从方程中得出，填表过程中需要得到前面的状态值，那么我们需要从左到右开始填表。
返回值：返回最大长度即可，在填表的过程中比较寻找即可
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ret = 1;
for(int i = 1; i < n; i++) {
for(int j = i-1; j >= 0; j--) {
if(nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
}
摆动序列
https://leetcode.cn/problems/wiggle-subsequence
状态表示：dp[i] 以 i 为结尾的 摆动子序列的最大长度，向前搜索，如果当 nums[j] > nums[i] 那么此时的差值为负数，我们后面要接一个结尾的差值为正数的子序列，这时候会发现现在这个 dp 表示不能满足。
我们需要细分 dp 值，f[i] 表示以 i 为结尾的 摆动子序列 且 最后一个差值为正数 的最大长度
g[i] 表示以 i 为结尾的 摆动子序列 且 最后一个差值为负数 的最大长度
状态转移方程推导：当 nums[i] > nums[j]， f[i] = Math.max(f[i], g[j] + 1)
当 nums[i] < nums[j]) g[i] = Math.max(g[i], f[j] + 1)
初始化：一个元素也可以构成摆动子序列，所以将两个 dp 表 初始化为 1
填表顺序：从左到右
返回值：返回两个 dp 表的最大值
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
Arrays.fill(f, 1);
Arrays.fill(g, 1);
int ret = 1;
for(int i = 1; i < n; i++) {
for(int j = i - 1; j >= 0; j--) {
if(nums[i] > nums[j]) {
f[i] = Math.max(f[i], g[j] + 1);
} else if(nums[i] < nums[j]) {
g[i] = Math.max(g[i], f[j] + 1);
}
}
ret = Math.max(ret, Math.max(f[i], g[i]));
}
return ret;
}
}
最长递增子序列的子数
https://leetcode.cn/problems/number-of-longest-increasing-subsequence
状态表示：这里使用两个 dp 表，len[i] 表示 以 i 结尾的元素的子序列的最大长度是多少
count[i] 表示 以 i 结尾的 最大长度的子序列有多少个
状态转移方程推导：len 很简单就是向前遍历 nums[i] > nums[j] 就判断是否要更新最大长度
count 就要小心谨慎，如果 nums[i] 跟新了最大长度，那么 此时 count[i] 应该等于 count[j]
如果遇到 nums[i] > nums[j] 且 最大长度不用更新，也就是说找到了另一个相同长度的子序列，这时候 count[i = count[j]
初始化：因为一个元素也可以构成一个序列，所以 len 表初始化为 1
由于一个元素可以构成一个序列，此时最大长度的序列就只有一个 ，count 表初始化为 1
填表顺序：因为要用到前面的状态值，所以从左到右开始填表
返回值：先记录最大长度，然后遍历 len 表找到最大长度的子序列，从 count 表获取序列个数，然后相加即可
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] len = new int[n];
int[] count = new int[n];
Arrays.fill(len, 1);
Arrays.fill(count, 1);
int ret = 0;
int max_len = 1;
for(int i = 1; i < n; i++) {
for(int j = i-1; j >= 0; j--) {
if(nums[i] > nums[j]) {
if(len[i] == len[j] + 1) {
count[i] += count[j];
} else if(len[i] < len[j] + 1) {
count[i] = count[j];
len[i] = len[j] + 1;
}
}
}
max_len = Math.max(max_len, len[i]);
}
for(int i = 0; i < n; i++) {
if(len[i] == max_len) {
ret += count[i];
}
}
return ret;
}
}
最长数对链
https://leetcode.cn/problems/maximum-length-of-pair-chain
解析：这道题目很像上面的最大长度的子序列问题，我们可以转化一下，先对二维数组进行升序排序，接下来就是常规的子序列问题了
class Solution {
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ret = 1;
for(int i = 1; i < n; i++) {
for(int j = i - 1; j >= 0; j--) {
if(pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ret = Math.max(ret, dp[i]);
}
return ret;
}
}
最长定差子序列
https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference
dp[i] 表示 以 i 元素为结尾的 最大长度的等差序列 的长度。
正常来说，我们需要加一个 向前遍历的 循环来找到 对应的等差数列， 当 nums[j] = nums[i] - difference 的时候，我们需要将 dp[i] 更新为 dp[j] + 1，为什么不需要进行 dp[i] = Math.max 的操作，因为这是定差等差数列，所以 nums[i] 前一个元素是唯一的，即使有很多个 nums[j] 满足 nums[i] 的条件也无所谓，在从后向前的循环中，我们只需要找到一个 nums[j] 就可以退出 j 的 循环。
处于后置位 的 nums[j] 的等差数列是一定包含 前置位的 nums[j] 的序列，并且后置位的 nums[j] 的长度是大于等于前置位的。
这里要注意超时问题，如果数据量过大，两次循环的时间就不行，那么我们需要进行优化，如何 快速得到nums[j] ？？？
这里可以使用 HashMap 来保存 nums[j] 和 j 下标
那么此时时间复杂度就为 O(N)
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int n = arr.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ret = 1;
Map<Integer, Integer> map = new HashMap<>();
map.put(arr[0], 0);
for(int i = 1; i < n; i++) {
if(map.containsKey(arr[i] - difference)) {
dp[i] = dp[map.get(arr[i] - difference)] + 1;
}
map.put(arr[i], i);
ret = Math.max(ret, dp[i]);
}
return ret;
}
}
最长的斐波那契子序列的长度
https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
构成斐波那契额数列的条件为 n > 3 , x1 + x2 = x3
因此斐波那契额数列至少需要三个元素，因此当返回值小于 3 的时候，这时候就没有斐波那契数列，直接返回 0
状态表示：从斐波那契数列构成的条件来看，需要三个数字，我们可以定义一个二维的 dp 表，dp[i][j] 表示以 i 和 j 结尾的元素的斐波那契数列的最大长度，因为只要确定最后两个元素，就可以确定 前一个 斐波那契数。
我们来固定一下，i 元素 是 起始元素，j 元素是 结尾元素，i 在 j 的前面
状态转移方程的推导：计算出 第三个斐波那契额数的 数值 arr[k] = arr[j] - arr[i]，k 要满足 k < j 这个条件
如何找到 arr[k] ，我们有两种思路，第一种就是加一层 for 循环，但是这样时间复杂度就变成了 n ^ 3
第二种思路就是使用 哈希表，保存 arr[k] 和 下标 k
dp[i][j] = max(dp[i][j], dp[k][i] + 1)
初始化：dp[i][j] 表示以 i 和 j 为结尾的斐波那契额数列，长度为 1 或者 2，我们可以直接将 dp 表初始化为 2，虽然当 i == j 的 dp 值是 1，但是这个数值我们是用不到的，因为我们填表的时候满足 i < j
填表顺序：
返回值：返回最大长度的 dp 值，当最大长度 小于 3 直接返回 0
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(dp[i], 2);
}
int ret = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(arr[0], 0);
map.put(arr[1], 1);
for(int j = 2; j < n; j++) {
for(int i = j - 1; i > 0; i--) {
int k = map.getOrDefault(arr[j] - arr[i], -1);
if(k != -1 && k < i) {
dp[i][j] = Math.max(dp[i][j], dp[k][i] + 1);
}
ret = Math.max(ret, dp[i][j]);
}
map.put(arr[j], j);
}
return ret < 3 ? 0 : ret;
}
}
最长等差数列
https://leetcode.cn/problems/longest-arithmetic-subsequence
和上一道题类似，dp[i][j] 表示以 i 和 j 元素结尾的等差数列的最大长度
使用哈希表进行优化
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(dp[i], 2);
}
Map<Integer, Integer> map = new HashMap<>();
map.put(nums[0], 0);
int ret = 2;
for(int i = 1; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int k = map.getOrDefault(2 * nums[i] - nums[j], -1);
if(k != -1 && k < i) {
dp[i][j] = Math.max(dp[i][j], dp[k][i] + 1);
}
ret = Math.max(ret, dp[i][j]);
}
map.put(nums[i], i);
}
return ret;
}
}
等差数列划分 Ⅱ - 子序列
https://leetcode.cn/problems/arithmetic-slices-ii-subsequence
dp[i][j] 表示 以 i 和 j 结尾的元素 【假定 i 在 j 后面】的等差数列一共有多少
状态转移方程推导：tmp = nums[j] - nums[i] ，开始向前遍历寻找 tmp, 把所有包含 tmp 的状态值获取，dp[i][j] += dp[k][i] + 1
dp[k][i] 表示以 k 和 i 元素为结尾的 等差数列，这里由于多出一个 j 元素，因此还需要加上 以 k, i ,j 这三个元素构成的等差数列，所以应要 + 1.
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
int ret = 0;
for(int i = 1; i < n; i++) {
for(int j = i + 1; j < n; j++) {
long tmp = (long)(2 * (long)nums[i]) - (long)nums[j];
for(int k = i - 1; k >= 0; k--) {
if(nums[k] == tmp) {
dp[i][j] += dp[k][i] + 1;
}
}
ret += dp[i][j];
}
}
return ret;
}
}