序列DP

leetcode 674 最长连续递增序列

原题链接:
https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/** 
    f[i] 以i结尾 长度最长的连续递增子序列
    本题要求的是  最长连续递增子序列
    连续 说明 f[i] 的状态只能由f[i - 1]转移而来
 */
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        int [] f = new int [n];
        Arrays.fill(f,1);
        int ans = 1;
        for(int i = 1 ; i < n ; i++){
            if(nums[i] > nums[i -1] ){
                f[i] = Math.max(f[i],f[i - 1] + 1);
            }
            ans = Math.max(ans,f[i]);
        }

        return ans;
    }
}

leetcode 62 不同路径

原题链接:
https://leetcode.cn/problems/unique-paths/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
    f[i][j] 表示 以i,j 坐标结尾的 机器人可以走的最多的路径情况
 */
class Solution {
    public int uniquePaths(int m, int n) {
        int [][] f = new int [m + 1][n + 1];
        // 初始到起点 只有一种走法
        f[1][1] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 1 ; j <= n ; j++){
                // f[i][j] = 1; 
                f[i][j] += f[i - 1][j] + f[i][j - 1]  ;
            }   
        }

        return f[m][n];
    }
}

leetcode 70 爬楼梯

原题链接:
https://leetcode.cn/problems/climbing-stairs/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
    f[i] 表示以当前 第i阶楼梯结尾 爬到楼顶的最大方案数
 */ 
class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }

        if(n == 2){
            return 2;
        }

        int []  f = new int [n + 1];

        f[1] = 1;
        f[2] = 2;


        for(int i = 3 ; i <= n ; i++){
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];
    }
}

leetcode 64 最小路径和

原题链接:
https://leetcode.cn/problems/minimum-path-sum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int [][] f = new int [m][n];

        for(int i = 0 ; i < m; i++){   
            for(int j = 0; j < n ; j++){
                if(i == 0 && j == 0){
                    f[i][j] = grid[i][j];
                }else if(i == 0){
                    f[i][j] = f[i][j - 1] + grid[i][j];
                }else if(j == 0){
                    f[i][j] = f[i - 1][j] + grid[i][j]; 
                }else{
                    f[i][j] = Math.min(f[i - 1][j],f[i][j - 1]) + grid[i][j];
                }
            }
        }

        return f[m - 1][n - 1];
    }
}

leetcode 368 最大整除子集

原题链接:
https://leetcode.cn/problems/largest-divisible-subset/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // 数组要有序
        // 否则 如果 nums[i] < nums[j] (i > j) 时无法正常判断倍数关系
        // 且状态也就失去了递推性
        Arrays.sort(nums);
        int n = nums.length;
        // dp数组 以i结尾的 符合题意要求的整数集的最大长度
        int [] f = new int [n];
        // 回溯数组 用于记录以i结尾 符合题意的整数集 状态是由哪一个状态而来
        int [] g = new int [n];

        for(int i = 0 ; i < n ; i++){
            int prev = i;
            int len = 1;
            for(int j = 0 ; j < n ; j++){
                if(nums[i] % nums[j] == 0 ){
                    if(len < f[j] + 1){
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            f[i] = len;
            g[i] = prev; 
        }

        int idx = -1;
        int max = -1;

        for(int i = 0 ; i < n; i++){
            if(f[i] > max){
                max = f[i];
                idx = i;
            }
        }

        List<Integer> ans = new ArrayList<>();

        while(ans.size() < max){
            ans.add(nums[idx]);
            idx = g[idx];
        }

        return ans;
    }
}

leetcode 300 最长递增子序列

原题链接:
https://leetcode.cn/problems/longest-increasing-subsequence/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int [] f = new int [n + 1];

        int ans = 1;

        for(int i = 0 ; i < n ; i++){
            f[i] = 1;
            for(int j = 0 ; j < i ; j++){
                if(nums[i] > nums[j]){
                    f[i] = Math.max(f[i], f[j] + 1);
                    ans = Math.max(ans,f[i]);
                }    
            }
        }

        return ans;
    }
}

53 最大子数组和

原题链接:
https://leetcode.cn/problems/maximum-subarray/?envType=daily-question&envId=2023-11-20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// f[i] 表示以nums[i]结尾的连续子数组的最大和

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int [] f = new int [n];
        f[0] = nums[0];
        int ans = f[0];
        for(int i = 1; i < n; i++){
            f[i] = Math.max(nums[i],f[i - 1] + nums[i]);
            ans = Math.max(ans,f[i]);
        }

        return ans;
    }
}

股票问题

leetcode 121. 买卖股票的最佳时机

这题可以用DP做 但不是最优解
最优解是枚举 只要有 后面的最大减前面最小的组合一组成立即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
    只能进行一次交易
    f[i][j] 表示以第i天结尾 持股状态为j的股票交易最大利润
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] f = new int [n][2];
        f[0][0] = 0;
        f[0][1] = -prices[0];

        for(int i = 1 ; i < n ; i++){
            f[i][0] = Math.max(f[i - 1][0],f[i - 1][1] + prices[i]);
            // 当前 由于只能进行一次操作 那么对应的前一次操作一定是买入 或者 之前买入但不动了 
            f[i][1] = Math.max(f[i - 1][1],-prices[i]) ;
        }

        return Math.max(f[n - 1][0],f[n - 1][1]);
    }
}

最优解 枚举 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int n = prices.length;
        int ans = 0;
        for(int i = 0 ; i < n ;i++){
            if(prices[i] < min){
                min = prices[i];
            }

            ans = Math.max(ans,prices[i] - min);
        }
        
        return ans;
    }
}

leetcode 122. 买卖股票的最佳时机 II

原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

用贪心做会更快一些 但dp也行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] f = new int [n][2];
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for(int i = 1 ; i < n;i++){
            f[i][0] = Math.max(f[i - 1][0],f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1],f[i - 1][0] - prices[i]);
        }

        return Math.max(f[n - 1][0],f[n - 1][1]);
    }
}

贪心解法

1
2
3
4
5
6
7
8
9
10
11
12
// 主要是理解交易的拆分性 一组跨越多段的交易 可以由一组连续的交易组合而成
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int n = prices.length;
        for(int i = 1 ; i < n ; i++){
            res += Math.max(0,prices[i] - prices[i - 1]);
        }

        return res;
    }
}

线性DP

leetcode 97. 交错字符串

原题链接:
https://leetcode.cn/problems/interleaving-string/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
    f[i][j] 表示使用s1的前i位 s2的前j位 (不包括第i位和第j位) 是否能拼凑出s3的前i+j位
    f[0][0] 代表1位都没有 
 */
class Solution {
    char [] cs(String s){
        return s.toCharArray();
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length();
        if(n + m != s3.length()){
            return false;
        }
        boolean [][] f = new boolean [n + 1][m + 1];
        // int l = n + m;
        f[0][0] = true;
        var cs1 = cs(s1);
        var cs2 = cs(s2); 
        var cs3 = cs(s3);

        // 初始化 省去边界判断 
        // 初始化时还要注意 如果前面一位无法组成 那么后续的肯定就无法满足条件 
        for(int i = 1 ; i <= n && f[i - 1][0] ; i++ ){
            f[i][0] = cs1[i - 1] == cs3[i - 1];
        }

        for(int i = 1; i <= m && f[0][i - 1]; i++){
            f[0][i] = cs2[i - 1] == cs3[i - 1];
        }

        for(int i = 1 ; i <= n ; i++){
            for(int j = 1 ; j <= m ; j++ ){  
                if(cs1[i - 1] == cs3[i + j - 1]){
                    f[i][j] |= f[i - 1][j];
                }

                if(cs2[j - 1] == cs3[i + j - 1]){
                    f[i][j] |= f[i][j - 1];
                }
            }
        }

        return f[n][m];
    }
}

跳跃游戏

leetcode 55. 跳跃游戏

原题链接:
https://leetcode.cn/problems/jump-game/

这题动态规划可以做 但不是最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// f[i] 表示以i结尾的点 当前可以到达的最远距离
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n <=  1){
            return true;
        }

        // 总长大于1  但只能永远停留在原地
        if(nums[0] == 0){
            return false;
        }

        int [] f = new int [n];
        f[0] = nums[0];
         for(int i = 1 ; i < n ; i++){
             f[i] = Math.max(f[i - 1],nums[i] + i);
             // 已经超过终点直接 返回true
             if(f[i] >= n - 1){
                 return true;
             }
             // 永远只能停留在原地 
             if(f[i] == i){
                return false;
             }
         }

         return true;
    }
}

一次遍历的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int k = 0;
        for(int i = 0 ; i < n ; i++){
            if(i > k){
                return false;
            }
            k = Math.max(k,i + nums[i]);
        }

        return true;
    }
}

leetcode 45. 跳跃游戏 II

原题链接:
https://leetcode.cn/problems/jump-game-ii/description/

DP可以做 但不是最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/** 
    f[i] 表示到达第i个位置所需要的最小步数
    类似于上升子序列模型
 */
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;    
        if(n <= 1){
            return 0;
        }

        int [] f = new int [n];
        Arrays.fill(f,Integer.MAX_VALUE);
        f[0] = 0;
        for(int i = 1 ; i < n; i++){
            for(int j = 0 ; j < i ; j++){
                // 可以到达当前点
                if(nums[j] >= i - j){
                    f[i] = Math.min(f[j] + 1,f[i]);
                }
            }
        }
        
        return f[n - 1];
    }
}

最优解
贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if(n <= 1){
            return 0;
        }

        // 当前可以到达的最远下一步 
        int next = 0;
        int end = 0;
        // 结果
        int ans = 0;

        // 根据题意 n - 1 就已经是终点了 且是一定到达的
        // 所以只要保证能走到 n - 2这个点 那么n - 1就一定是可达的
        // 反之如果保证了 走到 n - 1这个点 那么可能走到n - 2 就已经满足了条件了答案反而会多了一位
        for(int i = 0 ; i < n - 1 ; i++){
            next = Math.max(next,i + nums[i]);
            // 那么必须进行 下一跳 直接跳到最远距离 
            if(end ==  i){
                end =  next;
                ans++;
            }  
        }
        return ans;
    }
}

树形DP

acwing 285. 没有上司的舞会

原题链接:
https://www.acwing.com/problem/content/287/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static final int N = 6010;
    // 数组模拟链表
    public static int [] e, h, ne, happy;
    public static boolean [] has_father;
    public static int [][] f;
    public static int idx;

    public static void main(String[] args) {
        e = new int[N];
        ne = new int[N];
        h = new int[N];
        happy = new int [N];
        has_father = new boolean[N];
        // 初始化 链表
        Arrays.fill(h,-1);
        idx = 0;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        
        // 这里一定要从1开始 因为后续 root是1  同样也是防止出现f数组的越界问题
        for(int i = 1 ; i <= n ; i++){
            happy[i] = sc.nextInt();
        }

        for (int i = 0 ; i < n - 1 ; i++){
            // a , b  b是a上司
            int a,b;
            a = sc.nextInt();
            b = sc.nextInt();
            // b -> a  所以a 有根节点
            has_father[a] = true;
            add(b,a);
        }
        f = new int[N][2];

        int root = 1;
        while (has_father[root]){
            root++;
        }

        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));
    }

    public static void dfs(int u){
        // 选择这个节点作为根节点 则直接赋值
        f[u][1] = happy[u];

        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            // 先向下递归
            dfs(j);
            // 不选该节点
            // 则上一个节点可以选 也可以不选 取最大值即可
            f[u][0] += Math.max(f[j][0],f[j][1]);
            // 选了该节点 则上一个节点只能是不选
            f[u][1] += f[j][0];
        }
    }

    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}