两种木板任你挑，动态规划和二叉树再次结合巧解搭木板问题｜Java 刷题打卡

一、题目描述

======

面试题 16.11. 跳水板

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

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

示例 1

输入： shorter = 1 longer = 2 k = 3 输出： [3,4,5,6] 解释： 可以使用 3 次 shorter，得到结果 3；使用 2 次 shorter 和 1 次 longer，得到结果 4 。以此类推，得到最终结果。

二、思路分析

======

来由

--

• 这道题很贴近我们的生活，在我们平时很多场景都会遇到组合的问题。本题考查的考点也比较简单。官网提示需要用到的技能是递归、记忆化 。
• 这两种方式都可以解决问题。递归我们这里就不掩饰了。老生常谈的问题相信算法大家都会实现也不会是很复杂的。
• 首先我们构建一棵树，根节点是空组合。然后随着数的层级的递增在每个节点下都可以挂载连个节点分别是长木板、短木板。
• 我们将上图理解成二叉树。k代表二叉树的高度。而叶子节点就是我们最终结果集 。 所以说本题我们可以根据二叉树来存储从0-k所有的结果集。但是这样内存使用上肯定很高。因为我们需要存储很多不需要的数据
• 基于二叉树的分析，我们不难发现我们 只需要叶子节点。而且二叉树叶子结点也是有顺序的。我们不难发现二叉树叶子节点中最小值就是short*k。我们定义结果集数组为result[] 。 那么我们首先记住一个结论

result[0]\=shorter∗k;result[0] = shorter * k ;result[0]\=shorter∗k;

结果集

• 上面说了二叉树的叶子结点就是我们的结果集，这句话不是很准确。因为在叶子节点中会出现重复数据
• 上图中的两个叶子节点里跳水板的长度就是相同的。所以完全的叶子节点是不符合我们结果集的要求的。但是通过二叉树的特性我们分析得出了结果集的初始值
• 我们在回想本题，一共需要使用K跟木板。由长木板和短木板组合而成。那么针对长木板来说他的组合方案会有0~k个可能
• 所以我们的结果集长度就是K+1。而第一个元素是shorter*k。

变形的动态规划

• 到这里相信有的同学应该可以看出来有点像动态规划了。初始值是shorter*k 。长度是固定的。那么只要我们能确定转换方程就可以解决问题了。
• 应为只有两种模板选择，所以我们令i表示长木板的个数，此时i范围在[0,k] 。那么相对的短木板的数量就是k-i 。所以在长木板为i时长度为

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腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！