定义
命令模式(Command):属于行为型模式,将一个行为封装为一个对象,从而可以将行为与执行解耦,实现记录、撤销、排队等操作。
本题是第320场周赛的第四题,从题目的意思和数据范围可以看出需要使用动态规划求解,dp的描述也比较清晰,使用dp[i][j]表示前j个字符分成i段的方案数。提示到这里,小伙伴尝试自己写一下。
状态模式(State):属于行为型模式,允许对象的内部状态变化时改变其行为,使其看上去像改变自身所属类一样。
状态模式和策略模式类似,只不过状态模式更偏重于状态的自变化,策略模式强调策略的人为选择。如快递状态的变化,从打包->运输->存储;心情的变化,从生气->开心等。策略的变化如支付方法,选择微信或者支付宝,选择骑车、开车、还是步行等。
本题难度较大,不容易想到。一开始我想的是dp,从某一个位置i开始,找后面相同字符的位置j,那么在[i, j]区间中,回文子序列长度为5的个数等于[i + 1, j - 1]区间中,回文子序列长度为3的个数。因此可以先找长度为3的回文子序列个数,这样的时间复杂度是$ O(n^2) $,无法满足本题的范围。
本题是一个数学题,这个题目并不是很困难,很容易就想到要使用什么方法。这里提示一下,一个数可以整除a,那么第k个数就是a x k,如果一个数既可以整除a,又可以整除b,那么如何考虑呢?是否第a + b个数是a x b呢?