Easy
很明显，每次选择形成了一个二叉树，我们可以使用递归来做
python3
class Solution:
def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
r = []
def dfs(t, res):
if res <= 0:
r.append(t)
return
dfs(t + shorter, res - 1)
dfs(t + longer, res - 1)
dfs(0,k)
return list(set(r))
上面方法TLE了，我们可以发现其中有很多的重复计算：选了1，再选2 和 选了2，再选1对于结果来说是一样的
其中就有很多重复计算，而且k的范围是0 <= k <= 100000,这个二叉树的规模显然是不能直接使用递归来做的
换种思路
shorter * klonger * kdp[i]表示k中有i个长板子dp[i] = dp[i-1] + longer - shorter , i = [0,k]dp[0] = shorter * kk == 0的话，直接返回空数组shorter == longer，返回[shorter * k]以上，尝试写一下代码，AC！
python3
class Solution:
def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
if k is 0:
return []
if shorter is longer:
return [shorter * k]
dp = [0] * (k + 1)
dp[0] = shorter * k
for i in range(1,k+1):
dp[i] = dp[i-1] + longer - shorter
return dp