【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好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月份比賽正式開啟！機械鍵盤等你拿！