LC.P1105[填充书架]

方法一：动态规划(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int[][] books;
    int shelfWidth;

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

    private int dfs(int i) {
        if (i < 0) return 0;
        int ans = Integer.MAX_VALUE, maxHeight = 0, width = 0;
        for (int j = i; j >= 0; --j) {
            width += books[j][0];
            if (width > shelfWidth) break;
            maxHeight = Math.max(maxHeight, books[j][1]);
            ans = Math.min(ans, dfs(j - 1) + maxHeight);
        }
        return ans;
    }
}
  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(n)$

方法二：动态规划+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    int[][] books;
    int shelfWidth;
    int[] cache;

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

    private int dfs(int i) {
        if (i < 0) return 0;
        if (cache[i] != 0) return cache[i];
        int ans = Integer.MAX_VALUE, maxHeight = 0, width = 0;
        for (int j = i; j >= 0; --j) {
            width += books[j][0];
            if (width > shelfWidth) break;
            maxHeight = Math.max(maxHeight, books[j][1]);
            ans = Math.min(ans, dfs(j - 1) + maxHeight);
        }
        return cache[i] = ans;
    }
}
  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(n)$

方法三：递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] f = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i + 1] = Integer.MAX_VALUE;
            int maxHeight = 0, width = 0;
            for (int j = i; j >= 0; --j) {
                width += books[j][0];
                if (width > shelfWidth) break;
                maxHeight = Math.max(maxHeight, books[j][1]);
                f[i + 1] = Math.min(f[i + 1], f[j] + maxHeight);
            }
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$