Dynamic Programming II

 

Common dynamic programming problems (2)

This article is reproduced at GitHub address: https://github.com/CyC2018/CS-Notes/ , only for personal review in the future. Integrated various data, invasion and deletion.

Citation analysis:

Content from official account article: https://mp.weixin.qq.com/s/lKQI0aS1MBwfPujC-m_zkA

Use the dynamic programming trilogy to answer:

//Solution I
public int coinChange(int[] coins, int amount) {
    // Sub question:
    // f(k) = the minimum number of coins to round up the amount K
    
    // f(k) = min{ 1 + f(k - c) }
    // f(0) = 0
    int[] dp = new int[amount+1];
    Arrays.fill(dp, amount + 1); // Initialize DP array to positive infinity
    dp[0] = 0;
    for (int k = 1; k <= amount; k++) {
        for (int c : coins) {
            if (k >= c) {
                dp[k] = Math.min(dp[k], 1 + dp[k-c]);
            }
        }
    }
    // If DP [amount] > amount, it is considered an invalid element.
    if (dp[amount] > amount) {
        return -1;
    } else {
        return dp[amount];
    }
}

//Solution II
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) { //Change reverse order traversal to positive order traversal
            if (i == coin) {
                dp[i] = 1;
            } else if (dp[i] == 0 && dp[i - coin] != 0) {
                dp[i] = dp[i - coin] + 1;

            } else if (dp[i - coin] != 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == 0 ? -1 : dp[amount];
}

This problem is very troublesome for space optimization, so we ignore the fourth step of space optimization.

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target+1]; // Default initialization is 0
    dp[0] = 1; // Note base case
    for (int k = 1; k <= target; k++) {
        for (int n : nums) {
            if (k >= n) {
                dp[k] += dp[k-n];
            }
        }
    }
    return dp[target];
}

//Solution I
public int change(int amount, int[] coins) {
    int m = coins.length;
    int[][] dp = new int[m+1][amount+1];

    for (int i = 0; i <= m; i++) {
        for (int k = 0; k <= amount; k++) {
            if (k == 0) {
                dp[i][k] = 1; // base case
            } else if (i == 0) {
                dp[i][k] = 0; // base case
            } else {
                dp[i][k] = dp[i-1][k];
                if (k >= coins[i-1]) {
                    dp[i][k] += dp[i][k-coins[i-1]];
                }
            }
        }
    }
    return dp[m][amount];
}

//Solution II
public int change(int amount, int[] coins) {
    if (coins == null) {
        return 0;
    }
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

1.0-1 knapsack problem

There is a knapsack with a capacity of N, which is used to pack the items with the greatest value. These items have two attributes: Volume w and value v.

Define a two-dimensional array dp to store the maximum value, where dp[i][j] represents the maximum value that can be achieved when the volume of the first I items does not exceed j. Let the volume of the i-th item be w and the value be v. according to whether the i-th item is added to the backpack, it can be discussed in two cases:

  • The i-th item is not added to the backpack. The maximum value of the first i-1 item with a total volume of no more than j is the maximum value of the first i-1 item with a total volume of no more than j, dp[i][j] = dp[i-1][j].
  • Add the ith item to the backpack, dp[i][j] = dp[i-1][j-w] + v.

The ith item can be added or not, depending on which case has the greatest value. Therefore, the state transition equation of 0-1 knapsack is:

 

// W is the total volume of the backpack
// N is the number of items
// The weights array stores the weights of N items
// The values array stores the values of N items
public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N + 1][W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

Space optimization

0-1 knapsack can be optimized during program implementation. By observing the state transition equation, we can know that the state of the first I items is only related to the state of the first i-1 items. Therefore, dp can be defined as a one-dimensional array, where dp[j] can represent dp[i-1][j] or dp[i][j]. At this point,

Because dp[j-w] represents dp[i-1][j-w], dp[i][j-w] cannot be obtained first to prevent covering dp[i-1][j-w]. In other words, dp[i][j] should be calculated first and then dp[i][j-w], which needs to be solved circularly in reverse order during program implementation.

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    for (int i = 1; i <= N; i++) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= 1; j--) {
            if (j >= w) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    return dp[W];
}

The explanation of greedy algorithm cannot be used

The 0-1 knapsack problem cannot be solved by greedy algorithm, that is, it cannot be optimized by adding the most cost-effective items first, because this way may cause a waste of knapsack space, so it cannot be optimized. Consider the following items and a backpack with a capacity of 5. If you add item 0 first and then item 1, you can only store 16, wasting space of size 2. The best way is to store item 1 and item 2, with a value of 22

variety

  • Complete backpack: the number of items is unlimited

  • Multiple backpacks: limited number of items

  • Multidimensional cost backpack: items have not only weight, but also volume. At the same time, consider these two restrictions

  • Others: mutual restraint or dependence between items

1.1 divide the array into two parts equal to and

(force deduction 416) give a non empty array containing only positive integers. Whether the array can be divided into two subsets so that the sum of the elements of the two subsets is equal.

be careful:

There will be no more than 100 elements in each array
The size of the array will not exceed 200
Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: the array can be divided into [1, 5, 5] and [11]
 

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: an array cannot be divided into two elements and equal subsets

Solution: it can be regarded as a 0-1 knapsack problem with a knapsack size of sum/2.

Code implementation:

public boolean canPartition(int[] nums) {
    int sum = computeArraySum(nums);
    if (sum % 2 != 0) {
        return false;
    }
    int W = sum / 2;
    boolean[] dp = new boolean[W + 1];
    dp[0] = true;
    for (int num : nums) {                 // 0-1 backpack one item can only be used once
        for (int i = W; i >= num; i--) {   // From back to front, calculate dp[i] first and then dp[i-num]
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[W];
}

private int computeArraySum(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

1.2 change the sign of a group of numbers so that their sum is a given number

(force deduction 494) given a nonnegative integer array, A1, A2, An, and a target number, S. Now you have two symbols + and -. For any integer in the array, you can choose a symbol from + or -.

Returns the number of methods that can make the final array and add symbols to all of the target number S.

Example:

Input: num: [1, 1, 1, 1, 1], s: 3
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are five ways to make the final goal sum to 3.

Analysis: this problem can be transformed into a Subset Sum problem, which can be solved by using the 0-1 knapsack method.

This group of numbers can be regarded as two parts, P and N, where p uses a positive sign and N uses a negative sign. The following derivation is made:

                  sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                       2 * sum(P) = target + sum(nums)

Therefore, as long as we find a subset, make them all take a positive sign, and the sum is equal to (target + sum (Num)) / 2, it is proved that there is a solution.

Code implementation:

public int findTargetSumWays(int[] nums, int S) {
    int sum = computeArraySum(nums);
    if (sum < S || (sum + S) % 2 == 1) {
        return 0;
    }
    int W = (sum + S) / 2;
    int[] dp = new int[W + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int i = W; i >= num; i--) {
            dp[i] = dp[i] + dp[i - num];
        }
    }
    return dp[W];
}

private int computeArraySum(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return sum;
}

DFS solution:

public int findTargetSumWays(int[] nums, int S) {
    return findTargetSumWays(nums, 0, S);
}

private int findTargetSumWays(int[] nums, int start, int S) {
    if (start == nums.length) {
        return S == 0 ? 1 : 0;
    }
    return findTargetSumWays(nums, start + 1, S + nums[start])
            + findTargetSumWays(nums, start + 1, S - nums[start]);
}

1.3 the string with the most characters

(Li Kou 474) in the computer industry, we always pursue to obtain the maximum benefit with limited resources.

Now, suppose you control m , 0 , and n , 1 , respectively. In addition, there is an array containing only , 0 , and , 1 , strings.

Your task is to find the maximum number of strings that can be spelled out in the array by using the given , m , 0 , and n , 1. 0 and {0 are used at most once each.

be careful:

The number of given # 0 # and # 1 # will not exceed # 100.
The length of the given string array will not exceed 600.
Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: a total of 4 strings can be spelled out through 5 zeros and 3 1s, namely "10", "0001", "1", "0".
Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: you can spell "10", but there are no numbers left after that. A better choice is to spell "0" and "1".

This is a multi-dimensional cost 0-1 knapsack problem. There are two knapsack sizes, the number of 0 and the number of 1.

Code implementation:

public int findMaxForm(String[] strs, int m, int n) {
    if (strs == null || strs.length == 0) {
        return 0;
    }
    int[][] dp = new int[m + 1][n + 1];
    for (String s : strs) {    // Each string can only be used once
        int ones = 0, zeros = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                zeros++;
            } else {
                ones++;
            }
        }
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    return dp[m][n];
}

1.4 string segmentation by word list

(force deduction 139) given a non empty string s and a dictionary wordDict containing a list of non empty words, determine whether {s can be split into one or more words in the dictionary by spaces.

explain:

Words in the dictionary can be reused when splitting.
You can assume that there are no duplicate words in the dictionary.
Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: return true because "leetcode" can be split into "leetcode".
Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: return true because "applepenapple" can be split into "apple pen apple".
Note that you can reuse words in the dictionary.
Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Analysis: there is no limit on the number of words used in dict, so this is a complete knapsack problem.

This problem involves the use order of words in the dictionary, that is, items must be put into the backpack in a certain order. For example, the following dict is not enough to form the string "leetcode":

["lee", "tc", "cod"]

When solving the sequential complete knapsack problem, the iteration of the items should be placed in the innermost layer and the iteration of the knapsack should be placed in the outer layer. Only in this way can the items be placed in the knapsack in a certain order.

Code implementation:

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (String word : wordDict) {   // Iterations on items should be placed at the innermost level
            int len = word.length();
            if (len <= i && word.equals(s.substring(i - len, i))) {
                dp[i] = dp[i] || dp[i - len];
            }
        }
    }
    return dp[n];
}

1.5 combined sum

(force deduction 377) given an array composed of positive integers without duplicate numbers, find out the number of combinations of positive integers for the given target.

Example:

nums = [1, 2, 3]
target = 4

All possible combinations are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that sequences with different orders are treated as different combinations. Therefore, the output is 7.

Complete knapsack problem involving order.

Code implementation:

public int combinationSum4(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] maximum = new int[target + 1];
    maximum[0] = 1;
    Arrays.sort(nums);
    for (int i = 1; i <= target; i++) {
        for (int j = 0; j < nums.length && nums[j] <= i; j++) {
            maximum[i] += maximum[i - nums[j]];
        }
    }
    return maximum[target];
}

2. Stock trading

2.1 stock trading requiring a cooling off period

(Likou 309) give an integer array in which the ^ i ^ th element represents the stock price on ^ i ^ th day. ​

Design an algorithm to calculate the maximum profit. You can buy and sell as many shares as possible under the following conditions:

You cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).
After selling stocks, you can't buy stocks the next day (i.e. the freezing period is 1 day).
Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: the corresponding transaction status is: [buy, sell, frozen period, buy, sell]

Title Description: a one-day cooling time is required after the transaction.

Code implementation:

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }
    int N = prices.length;
    int[] buy = new int[N];
    int[] s1 = new int[N];
    int[] sell = new int[N];
    int[] s2 = new int[N];
    s1[0] = buy[0] = -prices[0];
    sell[0] = s2[0] = 0;
    for (int i = 1; i < N; i++) {
        buy[i] = s2[i - 1] - prices[i];
        s1[i] = Math.max(buy[i - 1], s1[i - 1]);
        sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
        s2[i] = Math.max(s2[i - 1], sell[i - 1]);
    }
    return Math.max(sell[N - 1], s2[N - 1]);
}

2.2 stock transactions requiring transaction fees

(force deduction 714) give an integer array , prices, in which the , i , element represents the stock price on the , i , day; The nonnegative integer {fee represents the handling fee for trading stocks.

You can complete transactions indefinitely, but you need to pay a handling fee for each transaction. If you have bought a stock, you can't continue to buy it until you sell it.

Returns the maximum profit.

Note: a transaction here refers to the whole process of buying, holding and selling stocks. You only need to pay a handling fee for each transaction.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: maximum profit that can be achieved:
Buy here {prices[0] = 1
Sell here prices[3] = 8
Buy here prices[4] = 4
Sell here prices[5] = 9
Total profit: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

Title Description: each transaction must pay a certain fee.

Code implementation:

public int maxProfit(int[] prices, int fee) {
    int N = prices.length;
    int[] buy = new int[N];
    int[] s1 = new int[N];
    int[] sell = new int[N];
    int[] s2 = new int[N];
    s1[0] = buy[0] = -prices[0];
    sell[0] = s2[0] = 0;
    for (int i = 1; i < N; i++) {
        buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
        s1[i] = Math.max(buy[i - 1], s1[i - 1]);
        sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
        s2[i] = Math.max(s2[i - 1], sell[i - 1]);
    }
    return Math.max(sell[N - 1], s2[N - 1]);
}

2.3 # stock transactions can only be conducted twice

(Likou 123, hard) given an array, its i-th element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can complete up to two {transactions.

Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: if you buy on the 4th day (stock price = 0) and sell on the 6th day (stock price = 3), this exchange can make a profit = 3-0 = 3.
Then, buy on the 7th day (stock price = 1) and sell on the 8th day (stock price = 4). This exchange can make a profit = 4-1 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: if you buy on the first day (stock price = 1) and sell on the fifth day (stock price = 5), this exchange can make a profit = 5-1 = 4.   
Note that you can't buy stocks on day 1 and day 2 and then sell them.   
Because this is involved in multiple transactions at the same time, you must sell the previous shares before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: in this case, no transaction is completed, so the maximum profit is 0.

Code implementation:

public int maxProfit(int[] prices) {
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    for (int curPrice : prices) {
        if (firstBuy < -curPrice) {
            firstBuy = -curPrice;
        }
        if (firstSell < firstBuy + curPrice) {
            firstSell = firstBuy + curPrice;
        }
        if (secondBuy < firstSell - curPrice) {
            secondBuy = firstSell - curPrice;
        }
        if (secondSell < secondBuy + curPrice) {
            secondSell = secondBuy + curPrice;
        }
    }
    return secondSell;
}

2.4 # only k stock transactions can be conducted

(Likou 188, hard) given an array, its i-th element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can complete up to k transactions.

Note: you cannot participate in multiple transactions at the same time (you must sell the previous shares before buying again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: if you buy on the first day (stock price = 2) and sell on the second day (stock price = 4), this exchange can make a profit = 4-2 = 2.
Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: if you buy on the second day (stock price = 2) and sell on the third day (stock price = 6), this exchange can make a profit = 6-2 = 4.
Then, buy on the 5th day (stock price = 0) and sell on the 6th day (stock price = 3). This exchange can make a profit of = 3-0 = 3.

Code implementation:

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {   // In this case, the stock trading problem is ordinary
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
    int[][] maxProfit = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        int localMax = maxProfit[i - 1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
            localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
        }
    }
    return maxProfit[k][n - 1];
}

3. String editing

3.1} delete the characters of two strings to make them equal

(force deduction 583) given two words , word1 , and , word2 , find the minimum number of steps required to make , word1 , and , word2 , the same, and one character in any string can be deleted in each step.

Example:

Input: "sea", "eat"
Output: 2
Explanation: the first step is to change "sea" into "ea", and the second step is to change "eat" into "ea"

It can be converted to the problem of finding the longest common subsequence of two strings.

Code implementation:

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return m + n - 2 * dp[m][n];
}

3.2 edit distance

(Likou 72, hard) here are two words , word1 and , word2. Please calculate the minimum operand used to convert , word1 , into , word2.

You can perform the following three operations on a word:

Insert a character
Delete a character
Replace one character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
Horse - > horse (replace 'h' with 'r')
Rose - > Rose (delete 'r')
Rose - > ROS (delete 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
Intent - > intent (delete't ')
Inention - > enention (replace 'i' with 'e')
Generation - > exception (replace 'n' with 'x')
Exception - > exception (replace 'n' with 'c')
Execution - > execution (insert 'u')

Title Description: modify a string to become another string to minimize the number of modifications. One modification operation includes inserting a character, deleting a character and replacing a character.

Code implementation:

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 1; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }
    return dp[m][n];
}

3.3 copying and pasting characters

(Likou 650) initially, there was only one character 'A' on A notepad. You can perform two operations on this Notepad at A time:

Copy All: you can Copy All characters in this Notepad (partial copying is not allowed).
Paste: you can paste the last character you copied.
Given A number, n. You need to use the least number of operations to print exactly n 'A' in Notepad. The output can print out the minimum number of operations of n# A's.

Example 1:

Input: 3
Output: 3
Explanation:
Initially, we had only one character 'A'.
In step 1, we use the Copy All operation.
In step 2, we use the Paste operation to obtain 'AA'.
In step 3, we use the Paste operation to obtain 'AAA'.

Code implementation:

public int minSteps(int n) {
    if (n == 1) return 0;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return i + minSteps(n / i);
    }
    return n;
}
public int minSteps(int n) {
    int[] dp = new int[n + 1];
    int h = (int) Math.sqrt(n);
    for (int i = 2; i <= n; i++) {
        dp[i] = i;
        for (int j = 2; j <= h; j++) {
            if (i % j == 0) {
                dp[i] = dp[j] + dp[i / j];
                break;
            }
        }
    }
    return dp[n];
}

 

Tags: Java Algorithm leetcode Dynamic Programming

Posted by h123z on Sun, 22 May 2022 21:13:49 +0300