動态規劃-01背包-Tallest Billboard

2020-02-07 17:46:32

問題描述：

問題求解：

解法一：BF

看問題規模看似可以直接暴力解決。

如果直接去解肯定是會逾時的，因為每次将原空間劃分成A區域，B區域和剩餘區域的時間複雜度為O(3 ^ n)。

但是我們可以将問題進行一下轉化，之前有個問題是能否将一個數組中的數劃分成兩個和相等的子區域那個題目是可以使用dp完成求解的，時間複雜度是O(nsum)。

是以我們可以去構造出所有的挑選可能，并對每個可能産生解的可能去過一遍dp就能完成本題。

但是，本解法并不是最優解。

int ret = 0;
    int[] nums;
    List<Integer> res = new ArrayList<>();
    
    public int tallestBillboard(int[] rods) {
        nums = rods;
        helper(0, 0);
        return ret;
    }
    
    private void helper(int start, int sum) {
        if (start >= nums.length) return;
        if (sum % 2 == 0 && check(res, sum / 2)) {
            ret = sum / 2;
        }
        helper(start + 1, sum);
        res.add(nums[start]);
        sum += nums[start];
        if (sum % 2 == 0 && check(res, sum / 2)) {
            ret = sum / 2;
        }
        helper(start + 1, sum);
        sum -= nums[start];
        res.remove(res.size() - 1);
    }
    
    private boolean check(List<Integer> nums, int target) {
        if (target <= ret) return false;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int w = target; w >= num; w--) {
                dp[w] |= dp[w - num];
            }
        }
        return dp[target] == 1;
    }      

解法二：DP

事實上，本題可以直接使用dp求解。時間複雜度O(nSum)，但是狀态的定義有點特殊。

dp[i][j] : 取前i個數字，diff = j的最大公共區域。

int inf = (int)1e9;
    public int tallestBillboard(int[] rods) {
        int n = rods.length;
        int sum = 0;
        for (int num : rods) sum += num;
        int[][] dp = new int[n + 1][sum + 1];
        for (int i = 0; i <= n; i++) Arrays.fill(dp[i], -inf);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum - rods[i - 1]; j++) {
                // not use i
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                // put on higher part
                dp[i][j + rods[i - 1]] = Math.max(dp[i][j + rods[i - 1]], dp[i - 1][j]);
                // put on lower part
                dp[i][Math.abs(j - rods[i - 1])] = Math.max(dp[i][Math.abs(j - rods[i - 1])], dp[i - 1][j] + Math.min(j, rods[i - 1]));
            }
        }
        return dp[n][0];
    }