# \[面试题 16.11]\[简单] 跳水板

## 题目描述

[面试题 16.11. 跳水板](https://leetcode-cn.com/problems/diving-board-lcci/)

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

示例：

```
输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}
```

提示：

* 0 < shorter <= longer
* 0 <= k <= 100000

## 解题思路

### 公式

如果有$$i$$块`shorter`木板, 就有$$k-i$$块`longer`木板, 所以总长度可以用公式表示.

```python
class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        return ([shorter * (k - i) + longer * (i) for i in range(k + 1)] if shorter != longer else [shorter * k])  if k > 0 else []
```

### 递归

本题真正想考察的方案. 但该方案会超时. - -

```python
class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        if k == 0:
            return []
        if shorter == longer:
            return [shorter * k]

        res = []
        seen = set()
        def func(remains, current, count_s, count_l):
            if remains == 0:
                res.append(current)
                return
            if (count_s + 1, count_l) not in seen:  # 注意剪枝
                seen.add((count_s + 1, count_l))
                func(remains - 1, current + shorter, count_s + 1, count_l)
            if (count_s, count_l + 1) not in seen:
                seen.add((count_s, count_l + 1))
                func(remains - 1, current + longer, count_s, count_l + 1)
        func(k, 0, 0, 0)
        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/di-gui/16.11-tiao-shui-ban.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.