原题链接：
https://leetcode-cn.com/problems/diving-board-lcci/
题目描述
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例1：
输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。
提示：
- 0 < shorter <= longer
- 0 <= k <= 100000
解题思路
此类求多少种可能性的题目一般都有 递推性质
即 f(n) 和 f(n-1)…f(1)之间是有联系的。
- 设跳上n级台阶有f(n)种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上1级或2级台阶。
- 当为1级台阶时： 剩余n-1个台阶，共f(n-1)种跳法。
- 当为2级台阶时： 剩余n-2个台阶，共f(n-2)种跳法。
- f(n)=f(n-1)+f(n-2).与斐波那契数列性质等价。
思路：
- 如果 k=0，则不能建造任何跳水板，因此返回空数组。
- 如果shorter和longer相等,则建造的跳水板的长度是唯一的，都等于shorterk，因此返回长度为1的数组，数组中的元素为shorterk。
- 如果shorter<longer，因为总共使用k个跳水板，则总共有k+1种组合。
第一种为k个shorter,然后shorter数量依次递减，longer的数量依次递增。保证两种跳水板的数量和为k。
C语言代码：
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* divingBoard(int shorter, int longer, int k, int* returnSize){if(k==0){ //如果 k=0，则不能建造任何跳水板，因此返回空数组。*returnSize=0;return NULL;}else if(shorter==longer){//若shorter和longer相等,则建造的跳水板的长度是唯一int* p = (int*)malloc(sizeof(int));*p = shorter * k;*returnSize = 1;return p;}else{//shorter<longer*returnSize = k + 1;int* lengths = (int*)malloc(sizeof(int) * (k + 1));for (int i = 0; i <= k; ++i) {lengths[i] = shorter * (k - i) + longer * i;}return lengths;}
}
