再问一个题目 还是黑书上的动态规划
在整数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道题，好几天了，实在没办法了才来求教，这个式子以及这个这类式子怎么推出来啊？？
拜托了！！先谢谢各位了
[解决办法]
