DP - LIS - 《学习笔记》

最长上升子序列，一种DP问题，给一个乱序数组，问最长(严格)上升/下降子序列的长度/个数(可重复/不可重复)

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

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路：
方法1：暴力DP，时间复杂度O(n2)
方法2：二分优化，时间复杂度O(nlogn)

// 方法1
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
            max = Math.max(max, f[i]);
        }
        return max;
    }
}

//方法2
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> q = new ArrayList<>();
        for (int x : nums) {
            if (q.isEmpty() || x > q.get(q.size() - 1))
                q.add(x);
            else {
                int l = 0, r = q.size() - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (q.get(mid) < x)
                        l = mid + 1;
                    else
                        r = mid;
                }
                q.set(r, x);
            }
        }
        return q.size();
    }
}

Acwing. 1012. 友好城市

经典LIS应用！！！

673. 最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

思路：
问最长上升子序列的个数，可重复
数据范围不超过2000，直接暴力DP即可

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n =  nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1, res = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j]; 
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            if (f[i] > max) {
                max = f[i];
            }
        }
        for (int i = 0; i < n; i++) {
            if (f[i] == max)
                res += g[i];
        }
        return res;
    }
}

Acwing 314. 低买

给定一段时间内股票的每日售价（正 16 位整数）。
你可以选择在任何一天购买股票。
每次你选择购买时，当前的股票价格必须严格低于你之前购买股票时的价格。
编写一个程序，确定你应该在哪些天购进股票，可以使得你能够购买股票的次数最大化。
例如，下面是一个股票价格时间表：
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87
如果每次购买都必须遵循当前股票价格严格低于之前购买股票时的价格，那么投资者最多可以购买四次该股票。
买进方案之一为：
Day 2 5 6 10
Price 69 68 64 62
输入格式
第 1 行包含整数 N，表示给出的股票价格的天数。
第 2 至最后一行，共包含 N 个整数，每行 10 个，最后一行可能不够 10 个，表示 N 天的股票价格。
同一行数之间用空格隔开。
输出格式
输出占一行，包含两个整数，分别表示最大买进股票次数以及可以达到最大买进次数的方案数。
如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案（只计算一次）。
数据范围
1≤N≤5000
输入样例1：
12 68 69 54 64 68 64 70 67 78 62 98 87
输出样例1：
4 2
输入样例2：
5 4 3 2 1 1
输出样例2：
4 1

思路：
完673的困难版，要求去重，只需在代码中间多加一个循环去重即可(PS：真不好想)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        int[] f = new int[n], g = new int[n];
        int max = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            //去重 例[5 4 3 1 3 1]
            //对于两个3来说，他们的下降子序列是完全一致的，需要将前一个3的子序列个数清空
            //这样在遍历到最后一个1时才不会重复加相同的子序列
            for (int j = 0; j < i; j++) {
                if (f[i] == f[j] && a[i] == a[j])
                    g[j] = 0;
            }
            max = Math.max(max, f[i]);
        }
        for (int i = 0; i < n; i++) {
            if (f[i] == max)
                cnt += g[i];
        }
        System.out.println(max + " " + cnt);
    }
}

873. 最长的斐波那契子序列的长度

如果序列 X1, X_2, …, X_n 满足下列条件，就说它是斐波那契式 _的：

n >= 3
对于所有 i + 2 <= n，都有 Xi + X{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：
输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。

提示：

3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 10^9

思路：
方法1：暴力枚举以所有两个数的为起始的最长斐波那契数列的长度，选最大值

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        Set<Integer> set = new HashSet<>();
        for (int x : arr)
            set.add(x);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i], b = arr[j];
                int len = 2;
                while (set.contains(a + b)) {
                    int t = a + b;
                    a = b;
                    b = t;
                    ans = Math.max(++len, ans);
                }
            }
        }
        return ans;
    }
}

方法2：DP，类似于LIS，但不完全一样。状态表示是二维，而转移是一维。
f[i][j]表示以a[i]和a[j]为最后两项的斐波那契数列的最大长度
状态转移, 其转移可以在O(1)时间内求出，存储一个值到下标的映射即可。

if (map.containsKey(a[i] - a[j] && map.get(a[i] - a[j]) < j)
        f[i][j] = f[j][i] + 1;

class Solution {
    public int lenLongestFibSubseq(int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = a.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++)
            map.put(a[i], i);
        int ans = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int x = a[i] - a[j];
                int idx = map.getOrDefault(x, -1);
                if (idx != -1 && idx < j) {
                    f[i][j] = Math.max(f[i][j], f[j][idx] + 1);
                    ans = Math.max(ans, f[i][j]);
                }
            }
        }
        return ans > 0 ? ans + 2 : ans;
    }
}

长为恰为3的最长上升子序列

题目描述：
求满足下列条件的序列个数：

长度为n
序列的每个元素值都在[1,m]
最长严格上升子序列的长度恰好为3

数据范围
3≤n≤1000
3≤m≤10

思路：
状态表示：f[i][a][b][c]表示长度为i的数组，且最长上升子序列长为1的末尾数字是a，最长上升子序列长为2的末尾数字是b，最长上升子序列长为3的末尾数字是c的方案数
初始化：f[0][m + 1][m + 1][m + 1] = 1 表示长为0的数组，不存在最长上升子序列，用m + 1表示不存在这一状态
状态转移：枚举第ii个元素的数值，记为x。若1≤x≤a，那么x可以替换a，则fi,x,b,c=fi,x,b,c+fi−1,a,b,c；若a+1≤x≤b，那么x可以替换b，则fi,a,x,c=fi,a,x,c+fi−1,a,b,c；若b+1≤x≤c，那么x可以替换c，则fi,a,b,x=fi,a,b,x+fi−1,a,b,c
注意：若a=m+1，表示长度为1的最长上升子序列不存在。b,c=m+1同理。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int mod = 998244353;
        int n = sc.nextInt(), m = sc.nextInt();
        int[][][][] f = new int[n + 1][m + 2][m + 2][m + 2];
        // 初始化
        f[0][m + 1][m + 1][m + 1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int a = 1; a <= m + 1; a++) {
                for (int b = 1; b <= m + 1; b++) {
                    for (int c = 1; c <= m + 1; c++) {
                        for (int x = 1; x <= a && x <= m; x++)
                            f[i][x][b][c] = (f[i][x][b][c] + f[i - 1][a][b][c]) % mod;
                        for (int x = a + 1; x <= b && x <= m; x++)
                            f[i][a][x][c] = (f[i][a][x][c] + f[i - 1][a][b][c]) % mod;
                        for (int x = b + 1; x <= c && x <= m; x++)
                            f[i][a][b][x] = (f[i][a][b][x] + f[i - 1][a][b][c]) % mod;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= m; j++)
                for (int k = 1; k <= m; k++)
                    res = (res + f[n][i][j][k]) % mod;
        System.out.println(res);
    }
}

Acwing 3499. 序列最大收益	一道类似于LIS的DP题