Integer Break: Unraveling Dynamic Programming

-
Here is the problem, by Leetcode. First try to think of the brute-force approach. https://leetcode.com/problems/integer-break/description/

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
The brute-force will certainly be exponential. This problem is screaming for a DP solution, but coming up with exactly the "formula" for it is the challenge.
Here is the way that I thought about the problem: as always, DP will be a construction approach, hence we'll build the solution for 1, 2, 3, ...., all the way to N, in our case N <= 58. Let's focus on a certain number N.
One possibility is clear: the solution for N might just be the best with 2 numbers only: (N-1)*1, or (N-2)*2, .... In general, (N-i)*i, for all i from 1 to N-1. But this only gives us the solution with 2 numbers in the addition. There might be many more numbers.
OK, in this case then, the other option is to assume that the solution for N-i has already been found with as many numbers as it gets, we just don't care, we simply assume that it exists. Let's assume that the solution has been stored in an array and we'll call that solution DP[N-i]. Well, in this case another possible alternative is DP[N-i] * i, right? Since we still need to add i to N-i to get to N.
In essence, the solution for DP[N] then becomes:

DP[N] = Max( (N-i) * i, DP[N-i] * i)

The picture below exemplifies this process:


With that in hands, all gosh, the code becomes a ridiculous (N^2)-time, N-space, 5-liners. Code is below, thanks, A.C.C.


public class Solution
{
 public int IntegerBreak(int n)
 {
  int[] dp = new int[n + 1];
  for (int i = 2; i <= n; i++)
   for (int j = 1; j < i; j++)
    dp[i] = Math.Max((i - j) * j, Math.Max(dp[i - j] * j, dp[i]));
  return dp[n];
 }
}

Comments

  1. TarasFebruary 4, 2019 at 6:25 PM

    That's a great general approach for solving this problem, but it can also be solved in a much more simple way by noting that in order to maximize the product of values that are greater than 4 it's always beneficial to chip off as many 3s as possible instead of using larger values. The proof of this fact is left as an exercise, but the solution is below:

    impl Solution {
    pub fn integer_break(n: i32) -> i32 {
    if n == 2 {
    return 1; // 1 * 1
    }
    if n == 3 {
    return 2; // 1 * 2
    }
    let mut product = 1;
    let mut tmp = n;
    while tmp > 4 {
    product *= 3;
    tmp -= 3;
    }
    return product * tmp;
    }
    }

    https://gist.github.com/ttsugriy/51d0b17a315ce14918df81c102ada808

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more