知识点指南

Dynamic Programming

Dynamic programming stores answers to smaller states so they can be reused. The key is defining what one state means and how earlier states produce the next state.

什么时候使用

读题时可以留意这些信号。

A choice now affects future choices.
The same subproblem appears many times.
A brute-force recursion would repeat work.

常见错误

提交前可以检查这些小陷阱。

Choosing a state that lacks needed information.
Forgetting base cases.
Using a future state before it has been computed.

怎么写成代码

把知识点翻译成变量、循环、判断和更新。

Define dp[i] in a sentence before coding.
Initialise base cases.
Loop through states in an order where needed previous states are already known.
Use a transition formula to fill each state.

在 Block 题里长什么样

答题时通常会看到这些步骤被拆成代码块。

1Read input.
2Create dp table/array.
3Set base cases.
4Loop through states.
5Apply transition from previous states.
6Output target dp value.

题目里怎么出现

读题时先找这些信号，再决定答案区应该选哪些 blocks。

The story counts ways or asks for best value under restrictions.
Local choices block or affect later choices.
The same suffix/prefix/state can be reached in multiple ways.

Choose or skip each position

一个小型模板，展示代码和 blocks 的对应关系。

C++

dp[0] = 0;
dp[1] = value[1];
for (int i = 2; i <= N; i++) {
    dp[i] = max(dp[i - 1], dp[i - 2] + value[i]);
}
cout << dp[N] << '\n';

Python

dp[0] = 0
dp[1] = value[1]
for i in range(2, N + 1):
    dp[i] = max(dp[i - 1], dp[i - 2] + value[i])
print(dp[N])

对应 block 顺序

1Define dp meaning.
2Create dp array.
3Set base cases.
4Loop over positions.
5Choose best transition.
6Output final dp state.