一、题目描述
======
你正在使用一堆木板建造跳水板。有两种类型的木板,其中长度较短的木板长度为shorter,长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法,生成跳水板所有可能的长度
返回的长度需要从小到大排列。
示例 1
输入: shorter = 1 longer = 2 k = 3 输出: [3,4,5,6] 解释: 可以使用 3 次 shorter,得到结果 3;使用 2 次 shorter 和 1 次 longer,得到结果 4 。以此类推,得到最终结果。
二、思路分析
======
来由
--
递归
、记忆化
。result[0]\=shorter∗k;result[0] = shorter * k ;result[0]\=shorter∗k;
结果集
K+1
。而第一个元素是shorter*k。变形的动态规划
f(i)\=shorter∗(k−i)+longer∗if(i) = shorter*(k-i) + longer * if(i)\=shorter∗(k−i)+longer∗i
f(i+1)−f(i)\=(shorter∗(k−(i+1))+longer∗(i+1))−(shorter∗(k−i)+longer∗i)\=shorter∗(−1)+longer∗1\=longer−shorterf(i+1)-f(i) = (shorter * (k-(i+1)) + longer * (i+1)) - (shorter*(k-i) + longer * i) = shorter * (-1) + longer * 1 = longer - shorterf(i+1)−f(i)\=(shorter∗(k−(i+1))+longer∗(i+1))−(shorter∗(k−i)+longer∗i)\=shorter∗(−1)+longer∗1\=longer−shorter
f(i+1)\=(longer−shorter)+f(i)f(i+1) = (longer-shorter) + f(i)f(i+1)\=(longer−shorter)+f(i)
三、AC 代码
=======
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) {
return new int[]{};
}
if (shorter == longer) {
return new int[]{shorter * k};
}
int[] arr = new int[k+1];
arr[0] = k * shorter;
for (int i = 1; i < arr.length; i++) {
arr[i] = (longer - shorter) + arr[i - 1];
}
return arr;
}
四、总结
====
我正在参与2023腾讯技术创作特训营第三期有奖征文,组队打卡瓜分大奖!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。