从[1..10]，这样的数字填10位与数量在第i个位置的方法具有1..to第i位值比最大值atmost 1更多最大值、数量、位置、数字
例如，如果我们考虑3位来自[1..3]数字的情况下......我们可以在5种方法做到这一点：
for example if we consider the case for 3 places with numbers from [1..3]..we can do it in 5 ways:
1 1 1
1 1 2
1 2 1
1 2 2
1 2 3
在第二位的，我们不能有3个为第12和1个第一名将之差大于1。
In second place we cant have 3 as the difference between 2nd and 1 first place will be more than 1.
在任何地方（比如我）可以拥有价值超过其previous位置值最大atmost 1以上（即从1 ..我-1）
Any place (say i ) can have value atmost 1 more than the LARGEST value at its previous positions (i.e from 1 ..i-1)
推荐答案
让 DP [I，J] =生成我的位置，使得最大为j有多少可能性，下面的限制。
我们有：
dp[0, 0] = dp[1, 1] = 1
dp[i, j > i] = dp[i > 0, 0] = 0
dp[2, 1] = 1*dp[1, 1] + dp[1, 0] <- add 1 at the end
dp[2, 2] = dp[1, 2] + dp[1, 1] <- add 2 at the end
dp[3, 1] = 1*dp[2, 1] + dp[2, 0] <- add 1 at the end
dp[3, 2] = 2*dp[2, 2] + dp[2, 1] <- add 2 at the end
dp[3, 3] = 3*dp[2, 3] + dp[2, 2] <- add 1, 2 or 3 at the end
sum = 1 + 2 + 1 + 1 = 5
dp[4, 1] = 1*dp[3, 1] + dp[3, 0]
dp[4, 2] = 2*dp[3, 2] + dp[3, 1]
dp[4, 3] = 3*dp[3, 3] + dp[3, 2]
dp[4, 4] = 4*dp[3, 4] + dp[3, 3]
sum = 1 + 6 + 1 + 3 + 3 + 1 = 15
dp[i, j] = j*dp[i - 1, j] + (1)
dp[i - 1, j - 1] (2)
answer = dp[n, 1] + dp[n, 2] + ... + dp[n, n]
（1）：我们有最大Ĵ的第 I - 1 元素了，所以我们可以把位置的任何我只要这并不违反规定。这事显然是： 1，...，J
(1): We have the max j for the first i - 1 elements already, so we can put anything on position i as long as this doesn't break the rule. This anything is clearly: 1, ..., j.
（2）：我们没有最大Ĵ的第 I - 1 ，所以我们必须让这样，通过追加Ĵ所有那些具有最大的J - 1 。注意，如果 1 ...我最大 - 1 是＆LT;的J - 1 ，我们不能 1 ...我是Ĵ以下，而这个问题的限制，所以没有一点考虑任何 DP [我 - 1，K＆LT; J - 1]
(2): We don't have the max j for the first i - 1, so we must make it so, by appending j to all those with a max of j - 1. Note that if the max of 1 ... i - 1 is < j - 1, we cannot make the max of 1 ... i to be j while following the restrictions of the problem, so there is no point considering any dp[i - 1, k < j - 1].
这可以在实施为O（n ^ 2），这应该是足够快的 N 起来大约5000上一个体面的CPU。所使用的内存也为O（n ^ 2）。
This can be implemented in O(n^2), which should be fast enough for for n up to about 5000 on a decent CPU. The memory used is also O(n^2).
