题目描述
有 n
根长度互不相同的木棍,长度为从 1
到 n
的整数。请你将这些木棍排成一排,并满足从左侧 可以看到 恰好 k
根木棍。从左侧 可以看到 木棍的前提是这个木棍的 左侧 不存在比它 更长的 木棍。
例如,如果木棍排列为 [1,3,2,5,4]
,那么从左侧可以看到的就是长度分别为 1
、3
、5
的木棍。
给你 n
和 k
,返回符合题目要求的排列 数目。由于答案可能很大,请返回对 10^9 + 7
取余 的结果。
样例
输入:n = 3, k = 2
输出:3
解释:[1,3,2], [2,3,1] 和 [2,1,3] 是仅有的能满足恰好 2 根木棍可以看到的排列。
输入:n = 5, k = 5
输出:1
解释:[1,2,3,4,5] 是唯一一种能满足全部 5 根木棍可以看到的排列。
输入:n = 20, k = 11
输出:647427950
解释:总共有 647427950 (mod 10^9 + 7) 种能满足恰好有 11 根木棍可以看到的排列。
限制
1 <= n <= 1000
1 <= k <= n
算法
(动态规划) $O(nk)$
- 设状态 $f(i, j)$ 表示使用了 $i$ 根木棍,满足从左侧可以看到恰好 $j$ 根木棍的方案数。
- 初始时,$f(0, 0) = 1$,其余待定。
- 转移时,对于 $f(i, j)$,不妨假设第 $i$ 根木棍是当前木棍中最短的。(这里的假设是合法的,因为任何一种状态总有最短的那个木棍)。
- 只有最短的木棍放到其余 $i - 1$ 根木棍的最左侧,才可以被看到,此时转移 $f(i, j) = f(i, j) + f(i - 1, j - 1)$;其余位置的放置都不会被看到,转移 $f(i, j) = f(i, j) + f(i - 1, j) * (i - 1)$。
- 最终答案为 $f(n, k)$。
时间复杂度
- 状态数为 $O(nk)$,转移时间为常数,故总时间复杂度为 $O(nk)$。
空间复杂度
- 需要 $O(nk)$ 的额外空间存储状态。
- 可以通过第二维倒序枚举,优化空间复杂度为 $O(k)$。
C++ 代码
#define LL long long
class Solution {
public:
int rearrangeSticks(int n, int k) {
const int mod = 1000000007;
vector<vector<int>> f(n + 1, vector<int>(k + 1, 0));
f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++)
f[i][j] = (f[i - 1][j - 1] + (LL)(f[i - 1][j]) * (i - 1)) % mod;
return f[n][k];
}
};
C++ 代码(空间优化)
#define LL long long
class Solution {
public:
int rearrangeSticks(int n, int k) {
const int mod = 1000000007;
vector<int> f(k + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = k; j >= 1; j--)
f[j] = (f[j - 1] + (LL)(f[j]) * (i - 1)) % mod;
f[0] = 0;
}
return f[k];
}
};