What is the main approach for solving the Kth Smallest Instructions problem?

The main approach involves using state transition dynamic programming to track the number of possible paths, combined with combinatorial calculations to directly compute the kth smallest lexicographic sequence.

How do you calculate the number of possible paths from a point to the destination?

The number of possible paths is calculated using binomial coefficients, specifically nCr(row - x + column - y, row - x), where (x, y) is the current point and (row, column) is the destination.

Why is dynamic programming important in solving this problem?

Dynamic programming helps by storing intermediate results, which avoids recomputing the number of paths multiple times, thus optimizing the solution and making it feasible for larger grids.

What are the constraints for the Kth Smallest Instructions problem?

The constraints are that destination.length == 2, 1 <= row, column <= 15, and 1 <= k <= nCr(row + column, row), where nCr is the binomial coefficient.

What happens if k exceeds the total number of possible paths?

If k exceeds the total number of paths from (0, 0) to (row, column), the problem would not have a valid kth sequence, and the answer should handle such edge cases.

#1643

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

第 K 条最小指令

Bob 站在单元格 (0, 0) ，想要前往目的地 destination ： (row, column) 。他只能向右或向下走。你可以为 Bob 提供导航指令来帮助他到达目的地 destination 。指令用字符串表示，其中每个字符： 'H' ，意味着水平向右移动 'V' ，意味…

数组数学动态规划组合数学

题目描述

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 个物品的不同方案数。

lightbulb

解题思路

方法一：组合计数

根据题目描述我们可以知道，最终的路径是由 $destination[0]$ 个 'V' 和 $destination[1]$ 个 'H' 组成的，且按字典序排列后的第 $k$ 条最小指令。

我们首先考虑字典序的最高位，即最左边的字符。如果高位字符是 'V'，那么所有以 'H' 开头的路径的字典序都比它小，而以 'H' 开头的路径总数为 $x = C_{v+h-1}^{h-1}$ 。

如果 $k \lt x$ ，那么高位字符一定是 'V'，我们将 $k$ 减去 $x$ ，并将 $v$ 减 $1$ ，然后继续考虑下一位字符；否则，高位字符一定是 'H'，我们将 $h$ 减 $1$ ，然后继续考虑下一位字符。

注意，如果 $h = 0$ ，那么高位字符一定是 'V'，因为剩下的字符都是 'V'。

问题可以转换为求解 $C_{n}^{k}$ ，我们可以通过公式 $C_{n}^{k} = C_{n-1}^{k-1} + C_{n-1}^{k}$ 递推求解。

时间复杂度 $O((h + v) \times h)$ ，空间复杂度 $O((h + v) \times h)$ 。其中 $h$ 和 $v$ 分别为 $destination[1]$ 和 $destination[0]$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of dynamic programming and combinatorics.
question_mark
The candidate efficiently applies binomial coefficients to reduce the problem complexity.
question_mark
The candidate navigates the state transition approach to solve the problem without brute-forcing all paths.

warning

常见陷阱

外企场景

error
Forgetting to consider the lexicographical order of instructions, leading to incorrect kth sequences.
error
Miscomputing the binomial coefficients, resulting in an inefficient or incorrect path count.
error
Not using dynamic programming to optimize the calculation of intermediate results, leading to unnecessary recomputation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given a different destination (row, column), how would the approach change?
arrow_right_alt
How would you modify the approach for finding the largest lexicographical instruction sequence?
arrow_right_alt
What happens if there are constraints on the number of right or down moves allowed?

help

常见问题

外企场景

继续练习

#1569 将子数组重新排序得到同一个二叉搜索树的方案数 #1735 生成乘积数组的方案数 #1467 两个盒子中球的颜色数相同的概率