遞歸算法之跳水闆

題目：

你正在使用一堆木闆建造跳水闆。有兩種類型的木闆，其中長度較短的木闆長度為shorter，長度較長的木闆長度為longer。你必須正好使用k塊木闆。編寫一個方法，生成跳水闆所有可能的長度。

Example:

輸入：
shorter = 1
longer = 2
k = 3
輸出： [3,4,5,6]
解釋：
可以使用 3 次 shorter，得到結果 3；使用 2 次 shorter 和 1 次 longer，得到結果 4 。以此類推，得到最終結果。      

代碼實作

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];

        if (shorter == longer) {
            return new int[]{shorter * k};
        }

        int[] length = new int[k+1];
        for(int i = 0; i <= k; i++){
            length[i] = shorter*(k - i) + longer*i;
        }
        return length;
    }
}      

解題思路

1. 由于短木闆和長木闆一共使用 kk 塊，是以一共有 k+1k+1 種組合，每種組合下建造的跳水闆長度都是不一樣的，一共有 k+1k+1 種不同的長度。

2. 是以建立長度為 k + 1 的數組 length, 對于 0<=i<=k 其中的關系為:

   length[i] = shorter*(k-i) + longer*i, length 包含跳水闆所有可能的長度。

• ​​使用 Google Breakpad 來助力解決程式崩潰​​
• ​​UE4 多人遊戲伺服器探索​​
• ​​使用虛幻引擎自動化工具實作自動化部署​​
• ​​如何在 UE4 中制作一扇自動開啟的大門​​
• ​​如何在 UE4 中用代碼去控制角色移動​​
• ​​如何給 UE4 場景添加遊戲角色​​
• ​​UE4：Android 平台開發實踐指南​​
• ​​UE4 開發避坑指南（持續更新）​​
• ​​新年開工啦，放個小煙花慶祝一下​​
• ​​聊聊與蘋果稽核員的愛恨情仇(下)​​
• ​​聊聊與蘋果稽核員的愛恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年終總結​​
• ​​二叉樹刷題總結：二叉搜尋樹的屬性​​
• ​​二叉樹總結：二叉樹的屬性​​
• ​​二叉樹總結：二叉樹的修改與構造​​
• ​​StoreKit2 有這麼香？嗯，我試過了，真香​​
• ​​看完這篇文章，再也不怕面試官問我如何構造二叉樹啦！​​
• ​​那幫做遊戲的又想讓大家氪金，太壞了！​​
• ​​手把手帶你撸一個網易雲音樂首頁 | 适配篇​​
• ​​手把手帶你撸一個網易雲音樂首頁（三）​​
• ​​手把手帶你撸一個網易雲音樂首頁（二）​​
• ​​手把手帶你撸一個網易雲音樂首頁（一）​​
• ​​代碼要寫注釋嗎？寫你就輸了​​
• ​​Codable釋出這麼久我就不學，摸魚爽歪歪，哎~就是玩兒​​
• ​​iOS 優雅的處理網絡資料，你真的會嗎？不如看看這篇​​
• ​​UICollectionView 自定義布局！看這篇就夠了​​

1. 關注公衆号--- HelloWorld傑少