这是 2020 年 8 月 15 日的每日一题。这道题我没写出来,是看题解的,这道题如果用常规的动态规划思路,很容易进入误区。特此记录一下。主要学到了以下两点:动态规划的 dp 函数可以是多元的,当二元无法表达状态转移的时候,尝试加多一维,具体第三维可以表示什么,这道题给出了一种思路。当动态规划的状态转移方向难以确定的时候,可以使用 递归 + 记忆化 的形式。虽然比迭代要占用更多的空间复杂度,但是

- 阅读全文 -