algorithm - 用 [1..10] 中的数字填充 10 个位置的方法，使得第 i 个位置的数字的值比 1.. 到第 i 个位置的最大值大 1

Question

例如，如果我们考虑 3 个地方的情况，其中数字来自 [1..3]..我们可以通过 5 种方式来实现:

1 1 1
1 1 2
1 2 1
1 2 2 
1 2 3

第二名我们不能有 3，因为第二名和第一名之间的差距将超过 1。

任何地方(比如 i )的值最多可以比其先前位置(即从 1 ..i-1 开始)的最大值大 1

Answer 1

让dp[i, j] = how many possibilities of generating i positions such that the max is j, following the restrictions .

我们有:

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):我们有最大值 j对于第一个i - 1元素已经存在，所以我们可以把任何东西放在位置 i只要这不违反规则。这什么都清楚:1, ..., j .

(2):我们没有最大值 j对于第一个i - 1 , 所以我们必须通过附加 j 来做到这一点对于所有最大值为 j - 1 的人.请注意，如果 1 ... i - 1 的最大值是< j - 1 , 我们不能使 1 ... i 成为最大值成为j同时遵循问题的限制，所以没有必要考虑任何 dp[i - 1, k < j - 1] .

这可以在 O(n^2) 中实现，对于 n 应该足够快了在一个像样的 CPU 上最多约 5000。使用的内存也是O(n^2) .