DP问题

发表于 Artalk： loading...
动态规划

动态规划问题简单集锦

重点，注意积累如何进行状态表示

acwing 898. 数字三角形

题目描述

image-20220318160307816

解析思路

  1. 不同的状态表示区分

例如，数字三角形这类路线问题，一般是路径上点的坐标。

  1. 集合的属性

一般是最大值、最小值、个数

本题目中是最大值

  1. 集合：从底向上走到 (i,j)(i,j) 的不同路径集合
  2. 状态是如何转移的–状态计算

代码

从底向上，无需边界控制。

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
import java.util.*;


class Main{
    static final int N = 510;
    static int[][] q = new int[N][N];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n;
        n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                q[i][j] = cin.nextInt();
            }
        }

        int[][] f = new int[n + 1][n + 1];
        for (int i = 0; i <= n; ++i) Arrays.fill(f[i], Integer.MIN_VALUE);
        for (int i = 0; i < n; ++i) f[n - 1][i] = q[n-1][i];
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
               f[i][j] = q[i][j] + Math.max(f[i+1][j], f[i+1][j + 1]);
            }
        }
        int res = Integer.MIN_VALUE;
        res = Math.max(res, f[0][0]);
        System.out.print(res);
    }
}

推荐从上到下计算

边界控制技巧

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
import java.util.*;


class Main{
    static final int N = 510;
    static int[][] q = new int[N][N];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n;
        n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                q[i][j] = cin.nextInt();
            }
        }

        int[][] f = new int[n][n];
        for (int i = 0; i < n; ++i) Arrays.fill(f[i], Integer.MIN_VALUE);
        f[0][0] = q[0][0];
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                // 注意以下边界控制
                if (j > 0) f[i][j] = Math.max(f[i - 1][j - 1] + q[i][j], f[i][j]);
                if (j < i) f[i][j] = Math.max(f[i][j], q[i][j] + f[i - 1][j]);
            }
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, f[n - 1][i]);
        }
        System.out.print(res);
    }
}

ACAC 后发现，每次状态转移其实都是在 f[i]f[i] 和 f[if[i-1]1] 之间，可以考虑优化空间占用，将 dpdp 数组优化成一维的

代码如下：

注意

二层循环处，跟01背包问题类似，一定要从后向前遍历

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
import java.util.*;


class Main{
    static final int N = 510;
    static int[][] q = new int[N][N];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n;
        n = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                q[i][j] = cin.nextInt();
            }
        }

        int[] f = new int[n];
        Arrays.fill(f, Integer.MIN_VALUE);
        
        f[0] = q[0][0];
        for (int i = 1; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                 int tmp = Integer.MIN_VALUE;
                if (j > 0) tmp = Math.max(f[j - 1], tmp);
                if (j < i) tmp = Math.max(tmp, f[j]);
                f[j] = tmp + q[i][j];
            }
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, f[i]);
        }
        System.out.print(res);
    }
}