序列化动态规划解题技巧总结
序列化动态规划属于动态规划中的基础题,这类题目通常是一组序列。
这类题目一般有一种比较通用的状态转移方程
$$
dp[i][aa]=Option_1^{i-1}(dp[i-1][bb])+cast_i
$$
其实这种题目在代码上也有一些小技巧
- 如果使用递推时间代码,让动态规划有效状态的下表从 1 开始,把下表 0 让给一步决策都没有做的初始状态。通常这样做,可以让边界处理简单不少。
- 其次是主动转移和被动转移,主动转移是从一个状态去找这个这个状态可以转移到什么状态;被动转移是去找这个状态是由什么状态转移来的。