今天继续复习搞基础课，加油！
树形DP
每一个节点都分为选和不选两种状态，选为f[i, 1]，不选为f[i, 0]，每一个节点想要最大，他的每一个子树权值都必须最大，递归即可
不选择根节点的最大值：
f
[
i
,
0
]
=
m
a
x
(
f
[
s
1
,
0
]
,
f
[
s
1
,
1
]
)
+
m
a
x
(
f
[
s
2
,
0
]
,
f
[
s
2
,
1
]
)
+
.
.
.
+
m
a
x
(
f
[
s
k
,
0
]
,
f
[
s
k
,
1
]
)
f[i, 0] = max(f[s1, 0], f[s1, 1]) + max(f[s2, 0], f[s2, 1]) +...+ max(f[sk, 0], f[sk, 1])
f[i,0]=max(f[s1,0],f[s1,1])+max(f[s2,0],f[s2,1])+...+max(f[sk,0],f[sk,1])
选择根节点的最大值：
f
[
i
,
1
]
=
f
[
s
1
,
0
]
+
f
[
s
2
,
0
]
+
f
[
s
3
,
0
]
+
.
.
.
.
.
+
f
[
s
k
,
0
]
f[i, 1] = f[s1, 0] + f[s2, 0] + f[s3, 0] + ..... + f[sk, 0]
f[i,1]=f[s1,0]+f[s2,0]+f[s3,0]+.....+f[sk,0]
AcWing 285. 没有上司的舞会 - AcWing
#includeusing namespace std; const int N = 6010; int n; int w[N]; int h[N], e[N], ne[N], idx; bool st[N]; // 用来判断是否有父节点，查找根节点 int f[N][2]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u) { f[u][1] = w[u]; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += max(f[j][0], f[j][1]); // 状态转移 f[u][1] += f[j][0]; } } int main(void) { cin >> n ; for (int i = 1 ; i <= n ; i ++) cin >> w[i]; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b ; cin >> a >> b ; add(b, a); st[a] = true; } int root = 1; while (st[root]) root++; //找到根节点 dfs(root); cout << max(f[root][0], f[root][1]) << endl ; return 0; }
记忆化搜索
顾名思义，就是把每一次搜索的过程中的有用信息都存下来，这样下一次搜索如果也要用到这个信息，就可以直接调用而不用再次搜索
AcWing 901. 滑雪 - AcWing
#includeusing namespace std; const int N = 310; int n, m; int h[N][N]; int f[N][N]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int dp(int x, int y) { int &v = f[x][y]; // v 等价于 f[x][y] if (v != -1) return v; // 如果他已经被搜过了，直接返回值 v = 1; // 至少为1 for (int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) v = max(v, dp(a, b) + 1); } return v; } int main(void) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &h[i][j]); } } memset(f, -1, sizeof f); // 表示每个状态都没有被算过 int res = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { res = max(res, dp(i, j)); } } cout << res << endl ; return 0; }
区间DP
区间dp ，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。
282. 石子合并 - AcWing题库
#includeusing namespace std; const int N = 310; int n; int s[N]; // 前缀和 int f[N][N]; int main(void) { cin >> n; for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1]; // 前缀和 for (int len = 2; len <= n; len++) { // 先枚举区间长度 for (int i = 1; i + len - 1 <= n; i++) { // 再枚举区间左端点 int j = i + len - 1; f[i][j] = 1e8; for (int k = i; k < j; k++) { // 枚举区间内每一种合并方式求最小 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]); } } } cout << f[1][n] << endl ; return 0; }
计数DP
类比完全背包问题，前i个物品中任选且体积恰好为j的方案数f[i, j]，对第i个物品进行分集合，选一个第i个物品使得体积恰好为j就是f[i, j - i]，选两个第i个物品使得体积恰好为j就是f[i, j - 2i]，以此类推方案数就是总和
f
[
i
,
j
]
=
f
[
i
−
1
,
j
]
+
f
[
i
,
j
−
i
]
+
f
[
i
,
j
−
2
∗
i
]
+
f
[
i
,
j
−
3
∗
i
]
+
.
.
.
+
f
[
i
,
j
−
s
∗
i
]
f[i, j] = f[i - 1, j] + f[i, j - i] + f[i, j - 2 * i] + f[i, j - 3 * i] + ... + f[i, j - s * i]
f[i,j]=f[i−1,j]+f[i,j−i]+f[i,j−2∗i]+f[i,j−3∗i]+...+f[i,j−s∗i]
利用完全背包优化方式：
f
[
i
,
j
−
i
]
=
f
[
i
−
1
,
j
−
i
]
+
f
[
i
,
j
−
2
∗
i
]
+
f
[
i
,
j
−
3
∗
i
]
+
.
.
.
+
f
[
i
,
j
−
s
∗
i
]
f[i, j - i] = f[i - 1, j - i] + f[i, j - 2 * i] + f[i, j - 3 * i] + ... +f[i, j - s * i]
f[i,j−i]=f[i−1,j−i]+f[i,j−2∗i]+f[i,j−3∗i]+...+f[i,j−s∗i]
可得：
f
[
i
,
j
]
=
f
[
i
−
1
,
j
]
+
f
[
i
,
j
−
i
]
f[i, j] = f[i - 1, j] + f[i, j - i]
f[i,j]=f[i−1,j]+f[i,j−i]
然后优化成一维空间，变成 f [ j ] = f [ j ] + f [ j − i ] f[j] = f[j] + f[j - i] f[j]=f[j]+f[j−i]即可
AcWing 900. 整数划分 - AcWing
#includeusing namespace std; const int N = 1010, mod = 1e9 + 7; int f[N]; int main(void) { int n; cin >> n; f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { f[j] = (f[j] + f[j - i]) % mod; } } cout << f[n] << endl ; return 0; }
