> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/di-gui/16.11-tiao-shui-ban.md).

# \[面试题 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
```