前言

想要精通算法和SQL的成長之路 - 系列導航

一. 填充書架

原題鏈接

題目中有一個值得注意的點就是：

• 需要按照書本順序擺放。
• 每一層當中，只要厚度不夠了，當前層最高的那一本書籍就視為本層的高度。

那么我們假設(shè)dp[i]： 代表從 book[0] 擺到 book[i] 的時書架的最小高度。

• 假設(shè)最后一層的第一本書的下標是 j，那么之前所有書本擺放的最小高度就是 dp[j-1]。
• 我們再計算出，下標在[j,i]（最后一層）的書本中，高度最高的那一本書（同時滿足厚度不超過shelfWidth），高度為maxHeight。
• 那么當前的最小總高度是 res = Max(dp[i-1]+maxHeight，res)。即之前的總高度+最后一層的最高高度。

我們遞歸，從后往前遞歸。入?yún)楸闅v的書本下標。

1. 終止條件：下標 <0。代表沒有書本了，停止遞歸。
2. 遞歸做的事情：循環(huán)[0,i]之間的所有元素，從后往前把書本放入最后一層，一旦厚度超出，終止遍歷。否則，計算當前層的最高高度以及最小總高。

public class Test1105 {
    public int[][] books;
    public int shelfWidth;

    public int minHeightShelves(int[][] books, int shelfWidth) {
        this.books = books;
        this.shelfWidth = shelfWidth;
        return dfs(books.length - 1);
    }

    public int dfs(int i) {
        // 終止條件
        if (i < 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE, maxHeight = 0, width = shelfWidth;
        for (int j = i; j >= 0; j--) {
            // 從后往前放書本
            width -= books[j][0];
            // 厚度不能超過 shelfWidth ，超過就代表放不下了
            if (width < 0) {
                break;
            }
            // 當前層最高高度
            maxHeight = Math.max(maxHeight, books[j][1]);
            // 更新總最低書架高度 = 上層最小總高度 + 當前層最高高度
            res = Math.min(res, dfs(j - 1) + maxHeight);
        }
        return res;
    }
}

這個解答其實對于用例比較多的情況，是會超時的。

1.1 優(yōu)化

我們來看下上面代碼的不好的點：

• 每次dfs的時候，循環(huán)的范圍是：[0,j]。
• 循環(huán)內(nèi)部又每次調(diào)用了dfs遞歸，即dfs[j-1]。

整個遞歸函數(shù)，只用到了一個索引的參數(shù)，我們可以發(fā)現(xiàn)，索引為1,2,3…的遞歸，被重復調(diào)用了非常多次。以當前索引為3為例：

• 第一次遞歸范圍：[0,3]。
• 第二次遞歸范圍：[0,2]。
• 第三次遞歸范圍：[0,1]。
• …

那么我們可以用一個全局的變量去記錄每次dfs返回的結(jié)果即可:文章來源地址http://www.zghlxwxcb.cn/news/detail-733353.html

public class Test1105 {
    public int[][] books;
    public int shelfWidth;
    // 緩存dfs的結(jié)果
    public int[] dfsCache;

    public int minHeightShelves(int[][] books, int shelfWidth) {
        this.books = books;
        this.shelfWidth = shelfWidth;
        // 初始化
        dfsCache = new int[books.length];
        // 給個初始值，-1代表沒有被執(zhí)行過，即沒有緩存
        Arrays.fill(dfsCache, -1);
        return dfs(books.length - 1);
    }

    public int dfs(int i) {
        // 終止條件
        if (i < 0) {
            return 0;
        }
        // 如果是-1，代表這層值沒有執(zhí)行過，往下走。否則，說明有緩存了，直接返回
        if (dfsCache[i] != -1) {
            return dfsCache[i];
        }
        int res = Integer.MAX_VALUE, maxHeight = 0, width = shelfWidth;
        for (int j = i; j >= 0; j--) {
            // 從后往前放書本
            width -= books[j][0];
            // 厚度不能超過 shelfWidth ，超過就代表放不下了
            if (width < 0) {
                break;
            }
            // 當前層最高高度
            maxHeight = Math.max(maxHeight, books[j][1]);
            // 更新總最低書架高度 = 上層最小總高度 + 當前層最高高度
            res = Math.min(res, dfs(j - 1) + maxHeight);
        }
        // 緩存下當前結(jié)果
        dfsCache[i] = res;
        return dfsCache[i];
    }
}

到了這里，關(guān)于想要精通算法和SQL的成長之路 - 填充書架的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！