【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“107.难住Tom的问题”的解法探究。先来看一下题目内容：
题目详情
等级：困难
知识点：DP
查看题目：难住Tom的问题
Jerry和Tom在公园里感到很无聊，于是就开始研究起来题目了，Jerry有一个n+1个桶(1<=n<=300)，这些桶的编号为0,1,2,...,n，然后让Tom去构造这些桶(每个桶可以看作list)，必须要满足以下的三个要求：
1、对于第i个桶里，它里面有i个数ai，并且这些数不能大于x(1<=ai<=300)。
2、 对于第i-1个桶，它必须是第i个桶的子序列。
3、对于第i个桶，它的字典序要大于第i-1个桶。
问满足以上要求的方案有多少总，答案对y(2<=y<=1e9)取模。
输入三行数据，分别为n,x,y，意思同题意。
输出一个数，表示最终的方案数，答案对y取模。
示例1
输入：
2
3
100
输出：
12
解题方法：
拿样例来说2 3 100,说明有3个桶，第0个桶一定是空的，那么符合条件的有以下12种方案：
({0},{1},{1,1}),
({0},{1},{1,2}),
({0},{1},{1,3}),
({0},{1},{2,1}),
({0},{1},{3,1}),
({0},{2},{2,1}),
({0},{2},{2,2}),
({0},{2},{3,1}),
({0},{3},{3,1}),
({0},{3},{3,2}),
({0},{3},{3,3})，
这只是简单的列举出了所有的情况，我们需要从中推出转移方程。
以{0},{2}为例，要构造出第三个桶就相当于往第二个桶中插入一个数字；
那么如果这个数字插在2的左边，一定是要比2大的数才可以，如果插到右边对于这个情况来说没有限制条件，如果对于位数较多的数列来说也要考虑到字典序的因素。
所以我们考虑fi[p]中，i表示当前的长度，j表示取到的数字，p表示有p个位置可插。
一共有三种状态，当你的p没位置了就没有地方可插，那么这个数就不插了dpi[i] += dpi[p],这里的第三维为i是因为所有的数都比j+1小，所以插到哪里都是可以的，所以为i。
如果p不为0的话说明有地方可插，这时可以考虑插在这个地方或者不插这个地方，如果不插这个地方dpi[p-1]+=dpi[p]，如果插这个地方dpi+1[p]+=dpi[p]，这里还需要乘以p+1是因为还有p个位置。
时间复杂度： O(n^3)
空间复杂度： n^3
看完之后是不是有了答题思路了呢，快来练练手吧：107.难住Tom的问题
在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！
