动态规划问题简单集锦
重点,注意积累如何进行状态表示
题目描述
解析思路
- 不同的状态表示区分
例如,数字三角形这类路线问题,一般是路径上点的坐标。
- 集合的属性
一般是最大值、最小值、个数
本题目中是最大值
- 集合:从底向上走到 (i,j) 的不同路径集合
- 状态是如何转移的–状态计算
代码
从底向上,无需边界控制。
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); } }
|
AC 后发现,每次状态转移其实都是在 f[i] 和 f[i-1] 之间,可以考虑优化空间占用,将 dp 数组优化成一维的
代码如下:
注意
二层循环处,跟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); } }
|