课堂小结

动态规划 DP 构造状态，并记录各个状态对应的最优解，形成递推。DP 三要素：状态，状态转移方程（递推公式），初始条件。 二分答案：如果假设一个答案 ans 后，能较容易求出 ans 是否可行，则可以用二分答案，例如今天第二题，用 l ~ r 表示可能的答案区间，如果 mid = (l + r) // 2 是可行解，则记录 ans = mid 并让 l = mid + 1 以寻找更大解，反之 r = mid - 1