动态规划(五)

2020-10-11 本文已影响0人茶还是咖啡

Partition Equal Subset Sum

给定一个非空数组，其中所有的元素都是正整数，问，是否可以将这个数组的元素分成两部分，使得这两部分的和相等。
eg：

[1, 5, 11, 5],可以分成[1, 5, 5 ]和[11]两部分元素，返回true

[1, 2, 3, 5],无法将元素分成两部分使其相等，返回false

思路
该题为背包问题的简化版本，即背包的容量为数组中所有元素的和装满 sum/2 即可。
对应的状态转移方程为：

F(n,c)考虑将n个物品填满容量为c的背包。

F(i) = F(i-1,C)||F(i-1,C-W(i))

解释
F(i)代表考虑到第i个物品是否可以将背包填满。
W(i)代表第i个物品的重量，如果考虑将第i个物品放进背包，那么即为F(i-1,C-W(i)),如果不考虑将第i个物品放进背包，那么背包的重量即为考虑前i-1个物品的重量，即为，F(i-1,C),两者最终找到任意一个可以将背包填满的方式即可。

暴力破解

    private boolean partitionEqualSubSetSum(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2 == 1) {
            return false;
        }
        return partitionEqualSubSetSumCore(arr, sum / 2, arr.length - 1);
    }

    private boolean partitionEqualSubSetSumCore(int[] arr, int c, int index) {
        if (c == 0) {
            return true;
        }
        if (index < 0 || c < 0) {
            return false;
        }
        return partitionEqualSubSetSumCore(arr, c, index - 1) ||
                partitionEqualSubSetSumCore(arr, c - arr[index], index - 1);
    }

记忆化搜索

    private boolean partitionEqualSubSetSumWithMemo(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2 == 1) {
            return false;
        }
        // memo[i][c]代表i个物品是否可以将容量为c的背包填满
        // 0代表不能填满，1代表可以，-1代表未填充过
        int[][] memo = new int[arr.length][sum / 2+1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return partitionEqualSubSetSumWithMemoCore(arr, sum / 2, arr.length - 1, memo);
    }

    private boolean partitionEqualSubSetSumWithMemoCore(int[] arr, int c, int index, int[][] memo) {
        if (c == 0) {
            return true;
        }
        if (index < 0 || c < 0) {
            return false;
        }
        if (memo[index][c] != -1) {
            return memo[index][c]==1;
        }
        boolean res = partitionEqualSubSetSumWithMemoCore(arr, c, index - 1, memo) ||
                partitionEqualSubSetSumWithMemoCore(arr, c - arr[index], index - 1, memo);
        memo[index][c] = res ? 1 : 0;
        return res;
    }

动态规划

   private boolean partitionEqualSubSetSum(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        if (sum % 2 == 1) {
            return false;
        }
        int c = sum / 2;
        boolean[] memo = new boolean[c + 1];
        // 先尝试将第0个物品放进背包
        for (int i = 0; i <= c; i++) {
            memo[i] = i == arr[0];
        }
        // 分别将第1-n个物品放进背包
        for (int i = 1; i < arr.length; i++) {
            for (int j = c; j >= arr[i]; j--) {
                memo[j] = memo[i - 1] || memo[c - arr[i]];
            }
        }
        return memo[c];
    }

Coin Change

给定不同面值的硬币，问至少需要多少硬币可以凑够指定金额，算法返回这个数，如果无法凑成，返回-1，（硬币可以无限使用）
eg:
如给定硬币金额为[1,2,5] ,amount = 11,那么返回3，(1,5,5)
如给定硬币金额为[2]，amount = 3，那么返回-1

Combination Sum

给定一个整数数组，其中元素没有重复，问，有多少种可能，使得数组中的数字，能凑够一个整数target，
eg：
如：num[1,2,3] target = 4
可能返回的组合有[1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1]
算法返回7，
注意：顺序性

Ones and Zeros

给定一个字符串数组，数组中每个字符串都是0，1串，问，用m个0和n个1，最多可以组成多少个01串。
[约束]

m和n不超过 100

数组中元素个数不超过600

如：[10, 0001, 111001, 1, 0]
给定5个0和3个1最多可以组成4个元素，10，0001，1，0

如：[10, 0, 1],给定1个0和1个1，最多可以组成两个元素，即，0和1

Word Break

给定一个非空字符串s和一个非空的字符串数组wordDict，问能否使用wordDict中的不同字符串首尾连接，构成非空字符串s，假定wordDict中没有重复的字符串

如：s = "leetcode" wordDict = ["leet", "code"] 返回true

Target Sum

给定一个非空的数字序列，在这些数字前加上“+”或者“-”使得计算结果为给定的整数s，问一共有多少种可能。
如：nums = [1, 1, 1, 1, 1] s = 3 答案为5
-1+1+1+1+1
+1-1+1+1+1
+1+1-1+1+1
+1+1+1-1+1
+1+1+1+1-1