Java 中可见 K 根的重排木棍数量

给定 n 根从 1 到 n 标记的棒子，我们必须将它们排成一行，使得从左边恰好可以看到 k 根棒子。如果一根棒子比它前面的所有棒子都高，则它是可见的。任务是计算满足此约束的有效排列的数量。

示例 1

输入： n = 3, k = 2

输出： 排列棒子的方法数：3

解释： 有三种有效的方法：(1, 3, 2)、(2, 3, 1) 和 (3, 1, 2)，其中从左边恰好可以看到 2 根棒子。

示例 2

输入： n = 4, k = 2

输出： 排列棒子的方法数：11

解释： 将最长的棒子放在第一位固定了一个位置，剩下的棒子使用 dp[3][2] = 3 加上 (3 * dp[3][1] = 8) 来计算，总共 11 种方法。

示例 3

输入： n = 4, k = 3

输出： 排列棒子的方法数：6

解释： 最长的棒子必须放在第一位，剩下的棒子可以按 dp[3][2] = 3 种方式排列，或者 2 * dp[3][3] = 3 种方式，总共 6 种。

示例 4

输入： n = 5, k = 3

输出： 排列棒子的方法数：35

解释： 将最长的棒子放在第一位贡献 dp[4][2] = 11，将其插入其他位置会增加 4 * dp[4][3] = 24，总计 35 种方法。

方法 1：动态规划（自顶向下，带记忆化）

自顶向下动态规划（记忆化）方法是计算排列 n 根棒子使得恰好 k 根可见的方法数。思路是将问题分解成更小的子问题，并将已计算过的结果存储起来，以避免重复计算。

算法

步骤 1： 如果 n == k，则只有一种排列方式（所有棒子都必须按递增顺序排列）。

步骤 2： 如果 n == 0 或 k == 0，则无效，返回 0。

步骤 3： 递推关系

步骤 3.1： 将最长的棒子放在第一位：它总是可见的，因此剩余的 n-1 根棒子应该排列使得 k-1 根可见。这贡献了 dp(n-1, k-1) 种方法。

步骤 3.2： 将最长的棒子放在其他位置：最长的棒子不会增加可见棒子的数量。剩余的 n-1 根棒子排列使得恰好 k 根可见，并且我们可以将最长的棒子插入 (n-1) 个不同的位置。这贡献了 (n-1) * dp(n-1, k) 种方法。

dp(n, k) = dp(n − 1, k − 1) + (n − 1) × dp(n − 1, k)

步骤 4： 将结果存储在 HashMap 中以避免冗余计算。

步骤 5： 如果子问题 (n, k) 已经计算过，则返回其存储的值，而不是重新计算。

让我们在 Java 程序中实现上述步骤。

输出

 
Ways to arrange sticks: 3   

复杂度

时间复杂度： 程序的复杂度为 O(n x k)。这是因为每个 (n, k) 对最多计算一次并存储在 map 中。

空间复杂度： 程序的复杂度为 O(n x k)。这是因为递归 栈。

方法 2：自底向上动态规划

自底向上 动态规划 (DP) 方法维护一个二维 DP 表 dp[n][k]，其中 dp[i][j] 表示排列 i 根棒子使得从左边恰好可见 j 根的方法数。

算法

步骤 1： 定义 dp[i][j] 它存储排列 i 根棒子且有 j 根可见的方法数。

步骤 2： 基本情况

步骤 2.1： dp[0][0] = 1 （空排列，没有可见棒子）。

步骤 2.2： dp[i][0] = 0 对于 i > 0 （非空排列中不可能有 0 根可见棒子）。

步骤 2.3： dp[i][i] = 1 （排列 i 根棒子使得所有棒子都可见只有一种方法）。

步骤 3： 递推关系

步骤 3.1： 将最长的棒子放在第一位（总是可见），将问题简化为 dp[i-1][j-1]。

步骤 3.2： 将最长的棒子放在其他位置，使其不可见。剩余的 (i-1) 根棒子应该排列使得 j 根可见，我们可以用 (i-1) * dp[i-1][j] 种方法来完成。

步骤 3.3： 公式：dp[i][j] = dp[i−1] [j−1] + (i−1) × dp[i−1] [j]

步骤 4： 迭代 i 和 j 以使用公式计算值。

步骤 5： 返回 dp[n][k] 作为最终结果。

让我们在 Java 程序中实现上述步骤。

输出

 
Ways to arrange sticks: 3   

复杂度

时间复杂度： 程序的复杂度为 O(n x k)。因为填充 dp 表需要 n x k 次操作。

空间复杂度： 程序的复杂度为 O(n x k)。因为我们使用了一个大小为 (n+1) x (k+1) 的二维 DP 表。