再问一个题目 还是黑书上的动态规划
在整数1，2，…，N的排列中，有些排列满足性质A：该排列中除了最后一个整数以外的每一个整数后面都跟有（不必直接紧跟）一个同它相差为1的整数。例如：N = 4，排列1432是具有性质A的，而2431则不满足。
设有一个N个数的排列，已知其中P(P≤N)个位置上的数，求共有多少个这样的排列——在P个位置上具有已知的数，且具有上述性质A。例如：N = 4，且已知第1位、第2位分别是1和4，则1432，1423就是这样的两个排列。
通过枚举N比较小的时候满足题目的排列，发现一个规律：任何一个排列的后k位 （l≤k≤n）是若干连续整数组成的集合。可以用数学归纳法证明这个结论
进一步地，还可以证明只要满足任意后k位（l≤k≤n）是若干连续整数组成的集合，则这个排列一定符合题目要求。
下面给出时空复杂度均为O(n2)的算法

设d[s, r]表示满足下面条件的序列C的总数
为s, s+1…s+r-1的一个排列
任意后k位都是连续整数组成的集合
如果原问题中倒数第i个位置上的数已经确定为x（l≤i≤r），那么C的倒数第i个位置上的数也要是x。由加法原理得


然后给出的状态转移方程是这样的
d[s+1,r-1]; 倒数第r位为s
d[s,r]={ d[s,r-1]; 倒数第r位必须为r+s-1;
d[s,r-1]+d[s+1,r-1]; 倒数第r位不确定
0 ； 其他情况，不能保证后r-1位为连续整数，故无解

我菜鸟，这几天真快吐了，头发都抓下来不少了，就这么12道题，好几天了，实在没办法了才来求教，这个式子以及这个这类式子怎么推出来啊？？
拜托了！！先谢谢各位了



[解决办法]

引用:

因为我时间不多了，所以想一口吃个胖子，再慢慢消化、、、
引用:
DP要入门也不是拿这种题入门的啊

4楼是大牛,我是大弱.
状态表示应这样理解,d[s,r]表示在倒数第r位放某个数,这个数属于集合{s,...,s+r-1}
如果还不明白,那我就以第一个转移为例说一下.
d[s,r]=d[s+1,r-1](倒数第r位必须为s)
那我们就在倒数第r位上放s,接着我们考虑倒数第r-1位该放什么,放{s+1,s+1+(r-1)-1==s+r-1(我只放了s,{s+1,...,s+r-1还没放呢})}中的某个数.
所以,f[s,r]=f[s+1,r-1].
其它的状态转移方程同理(厄,名词乱用了)可得.