第 K 条最小指令

标签: 数组数学动态规划组合数学

难度: Hard

Bob 站在单元格 (0, 0) ，想要前往目的地 destination ：(row, column) 。他只能向右或向下走。你可以为 Bob 提供导航指令来帮助他到达目的地 destination 。

指令用字符串表示，其中每个字符：

'H' ，意味着水平向右移动
'V' ，意味着竖直向下移动

能够为 Bob 导航到目的地 destination 的指令可以有多种，例如，如果目的地 destination 是 (2, 3)，"HHHVV" 和 "HVHVH" 都是有效指令。

然而，Bob 很挑剔。因为他的幸运数字是 k，他想要遵循 按字典序排列后的第 k 条最小指令 的导航前往目的地 destination 。k 的编号 从 1 开始 。

给你一个整数数组 destination 和一个整数 k ，请你返回可以为 Bob 提供前往目的地 destination 导航的 按字典序排列后的第 k 条最小指令 。

示例 1：

输入：destination = [2,3], k = 1
输出："HHHVV"
解释：能前往 (2, 3) 的所有导航指令 按字典序排列后 如下所示：
["HHHVV", "HHVHV", "HHVVH", "HVHHV", "HVHVH", "HVVHH", "VHHHV", "VHHVH", "VHVHH", "VVHHH"].

示例 2：

输入：destination = [2,3], k = 2
输出："HHVHV"

示例 3：

输入：destination = [2,3], k = 3
输出："HHVVH"

提示：

destination.length == 2
1 <= row, column <= 15
1 <= k <= nCr(row + column, row)，其中 nCr(a, b) 表示组合数，即从 a 个物品中选 b 个物品的不同方案数。

Submission

运行时间: 28 ms

内存: 0.0 MB

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        ans = list()
        for i in range(h + v):
            if h > 0:
                o = math.comb(h + v - 1, h - 1)
                if k > o:
                    ans.append("V")
                    v -= 1
                    k -= o
                else:
                    ans.append("H")
                    h -= 1
            else:
                ans.append("V")
                v -= 1
        return "".join(ans)

Explain

这个题解使用数学组合的方法来确定第k个最小指令。通过计算在当前位置，选择向右移动（H）的不同方案数，可以判断第k个指令是选择H还是V。如果k大于向右移动的方案数，说明第k个指令肯定是V，否则就选择H。每次选择完一个指令，就更新剩余的k值以及剩余需要移动的水平和垂直步数，直到构建出完整的指令序列。

时间复杂度: O(h+v)

空间复杂度: O(h+v)

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        v, h = destination
        ans = list()
        
        # 遍历 h+v 次，构建指令序列
        for i in range(h + v):
            if h > 0:
                # 计算当前位置向右移动的方案数
                o = math.comb(h + v - 1, h - 1)
                if k > o:
                    # 如果 k 大于向右移动的方案数，选择向下移动
                    ans.append("V")
                    v -= 1
                    k -= o
                else:
                    # 否则选择向右移动
                    ans.append("H")
                    h -= 1
            else:
                # 如果只能向下移动，直接选择 V
                ans.append("V")
                v -= 1
        
        # 将指令序列转换为字符串并返回
        return "".join(ans)

Explore

数学组合方法被选择用来解决这个问题，因为它可以高效地计算在给定的指令序列中，每个可能的子序列的排列数量。这使得我们可以直接确定第 K 个最小指令是什么，而不需要生成所有可能的指令序列。这种方法比穷举法或深度优先搜索更高效，因为它避免了生成大量不必要的序列。此外，还可以使用优先队列（最小堆）和A*搜索算法，但这些算法在空间和时间复杂度上通常不如数学组合方法高效。

在计算数学组合时，参数 `math.comb(h + v - 1, h - 1)` 表示在剩余的 `h+v-1` 步中选择 `h-1` 步向右移动（H）的不同方案数。这里的 `h+v-1` 是因为我们在每次决定一个方向后，总步数减少1，而 `h-1` 是因为我们已经决定了一个向右的步数，所以剩余的步数中再选择 `h-1` 步向右。这样的组合计数可以帮助我们确定在当前步骤中向右还是向下，以确保我们按字典序正确选择每一步。

当 h 为 0 时，代码中直接添加 'V' 并减少 v 值的处理方式是正确的，因为在这种情况下，没有剩余的水平步数（H），所以所有剩余的步骤都必须是垂直向下（V）。这确保了当无法再向右移动时，算法正确地将所有剩余的步骤指向下移，完全符合题目要求。

在算法中，每次决策点的字典序位置是通过计算当前向右（H）移动的所有可能方案数来确定的。使用 `math.comb(h+v-1, h-1)` 计算从当前位置开始，如果选择向右的话，可以有多少种不同的路径。如果变量 k（表示我们要找的是第 k 小的路径）大于这个计算出的方案数，那么意味着我们需要在字典序上更进一步，选择向下（V）。如果 k 小于或等于这个方案数，则表明当前的第 k 小的路径需要向右。这样的决策过程确保了每一步都是按照字典序递增的方式选择的。