[LeetCode] 2140. Solving Questions With Brainpower

Problem: https://leetcode.com/problems/solving-questions-with-brainpower/description/

Similar to the House Robber problem. For each question, we need to consider these 2 cases:

The point we can get if we solve this problem and solve or skip the next eligible problem.

The point we can get if we skip this problem and solve or skip the next eligible problem.

Time Complexity : O ( N )

Space Complexity : O ( N )

class Solution {
    public long mostPoints(int[][] questions) {
        int N = questions.length;

        // maximum point when pick the 'i' question
        long[] pick = new long[N];
        // maximum point when skip the 'i' question
        long[] skip = new long[N];

        for (int i = N-1; i >= 0; i--) {
          // solve the 'i' question
          pick[i] = questions[i][0];

          int j = i + questions[i][1] + 1;
          if (j < N) {
            // add on the point of picking / skip next eligible question 
            pick[i] += Math.max(pick[j], skip[j]);
          }

          // skip the 'i' question
          if (i + 1 < N) {
            // add on the point of picking / skip the next question 
            skip[i] = Math.max(pick[i+1], skip[i+1]);
          }
        }

        return Math.max(pick[0], skip[0]);
    }
}

[LeetCode] 647. Palindromic Substrings

 Problem: https://leetcode.com/problems/palindromic-substrings/

class Solution {
    public int countSubstrings(String s) {
        int N = s.length();
        
        boolean[][] dp = new boolean[N][N];
        int result = 0;
        
        for (int i= N-1; i >= 0; i--) {
            for (int j = N-1; j >= i; j--) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1]);
                if (dp[i][j]) {
                    result += 1;
                }
            }
        }
        
        return result;
    }
}

[LeetCode] 1014. Best Sightseeing Pair

 Problem : https://leetcode.com/problems/best-sightseeing-pair/

Keep tracking the maximum score we encountered. Decrease the maximum score while iterating to right side.

class Solution {
    fun maxScoreSightseeingPair(values: IntArray): Int {
        var mxScore = values[0]
        var result = 0
        
        for (i in 1 until values.size) {
            mxScore -= 1
            
            result = maxOf(result, values[i] + mxScore)    
            mxScore = maxOf(mxScore, values[i])
        }
        
        return result
    }
}

[LeetCode] 1567. Maximum Length of Subarray With Positive Product

 Problem : https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

Positive A * Positive B -> Positive C

Negative A * Negative B -> Positive C

Keep tracking positive and negative product result sub-array length end by current number. 

Reset sub-array length when encounter '0'

class Solution {
    fun getMaxLen(nums: IntArray): Int {
        var positiveSoFar = 0
        var negativeSoFar = 0
        var result = 0
        
        for (n in nums) {
            if (n > 0) {
                positiveSoFar += 1
                negativeSoFar = if (negativeSoFar > 0) negativeSoFar + 1 else 0
            } else if (n < 0) {
                val prePositiveSoFar = positiveSoFar
                positiveSoFar = if (negativeSoFar > 0 ) negativeSoFar + 1 else 0
                negativeSoFar = prePositiveSoFar + 1
                
            } else {
                positiveSoFar = 0
                negativeSoFar = 0
            }
            
            result = maxOf(result, positiveSoFar)
        }
        
        return result
    }
}

[LeetCode] 918. Maximum Sum Circular Subarray

 Problem : https://leetcode.com/problems/maximum-sum-circular-subarray/

In a circular integer, the maximum sum of sub-array can exists in 2 parts:

AAABBBBA'A'A'

It may either exist in the contiguous sub-array [BBBB] or exists in the sub-array [A'A'A'AAA] which combined by the front and rear sub-arrays. 

It is easy to get maximum value of [BBBB].

The maximum value of [A'A'A'AAA] = total value - minimum value of [BBBB]

When the maximum value of [BBBB] <= 0, all numbers in the given array must <= 0.

The the total value == minimum 

The maximum sum of sub-array can only exist in [BBBB].

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        // maximum value of contiguous sub-array
        var mx = nums[0]
        var mxSoFar = nums[0]
        
        // minimum value of contiguous sub-array
        var mi = nums[0]
        var miSoFar = nums[0]
        
        for (i in 1 until nums.size) {
            mxSoFar = maxOf(mxSoFar + nums[i], nums[i])
            mx = maxOf(mx, mxSoFar)
            
            miSoFar = minOf(miSoFar + nums[i], nums[i])
            mi = minOf(mi, miSoFar)
        }
        
        // if mx > 0 :
        //     the maximum value either exists in one contiguous sub-array
        //     or existis in the combination of the front sub-array 
        //     and rear sub-array (= total - miSoFar)
        // if mx <= 0 :
        //     all numbers in the input array <= 0.
        //     mx is the maximum sum of sub-array 
        return if (mx > 0) maxOf(mx, nums.sum() - mi) else mx 
        
    }
}

[LeetCode] 828. Count Unique Characters of All Substrings of a Given String

 Problem : https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/

Instead of counting substrings, count the contribution of each unique character.

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        N = len(s)
        
        seen = defaultdict(lambda: -1)
        left = [0] * N   # the left side window in which the ith character is unique
        
        for i in range(N):
            left[i] = seen[s[i]]
            seen[s[i]] = i
        
        seen = defaultdict(lambda: N)
        right = [0] * N  # the right side window in which the ith character is unique
        
        for i in reversed(range(N)):
            right[i] = seen[s[i]]
            seen[s[i]] = i
        
        
        result = 0
        
        for i in range(N):
            # ith character can be unique in (left window size) * (right window size) substrings. 
            result += (i - left[i]) * (right[i] -i)
        
        return result
        

[LeetCode] 1137. N-th Tribonacci Number

 Problem : https://leetcode.com/problems/n-th-tribonacci-number/

Similar to Fibonacci number.

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0, 1, 1]
      
        for i in range(3, n+1):
            dp[0], dp[1], dp[2] = dp[1], dp[2], sum(dp)
        
        return dp[n] if n < 2 else dp[2]

[LeetCode] 764. Largest Plus Sign

 Problem : https://leetcode.com/problems/largest-plus-sign/

To solve this problem with brute force approach, we need to check length of the 4 arms of each cell and use the shortest arm as the length of the axis-aligned plus sign which be centered by current cell.

To avoid repeatedly calculating arm length, we can use prefix-sum to accelerate.

Time complexity = O ( N * N )

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        
        dp1 = [[0] * n for _ in range(n)]
        dp2 = [[0] * n for _ in range(n)]
        
        mineSet = {(y,x) for y, x in mines}
        
        for y in range(n):
            # left to right
            dp1[y][0] = 0
            for x in range(1, n):
                if (y, x) in mineSet or (y, x-1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = dp1[y][x-1] + 1
        
            dp1[y][-1] = 0 
            # right to left
            for x in reversed(range(n-1)):
                if (y, x) in mineSet or (y, x+1) in mineSet:
                    dp1[y][x] = 0
                else:
                    dp1[y][x] = min(dp1[y][x], dp1[y][x+1] + 1)
        
        for x in range(n):
            # top to bottom
            dp2[0][x] = 0
            for y in range(1, n):
                if (y, x) in mineSet or (y-1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = dp2[y-1][x] + 1
            
            dp2[-1][x] = 0
            # bottom to top
            for y in reversed(range(n-1)):
                if (y, x) in mineSet or (y+1, x) in mineSet:
                    dp2[y][x] = 0
                else:
                    dp2[y][x] = min(dp2[y][x], dp2[y+1][x] + 1)
        
        result = 0
        
        for y in range(n):
            for x in range(n):
                if (y, x) not in mineSet: 
                    result = max(result, min(dp1[y][x], dp2[y][x]) + 1)
        
        return result

[LeetCode] 256. Paint House

 Problem : https://leetcode.com/problems/paint-house/

Let the state dp[i] as minimum cost by using color i to paint current house. Because current state is decided by the last state. This problem can be solved by DP solution. 

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        N = len(costs)
        dp = costs[0]
        
        for i in range(1, N):
            dp = [min(dp[1], dp[2]) + costs[i][0], min(dp[0], dp[2]) + costs[i][1], min(dp[0], dp[1]) + costs[i][2]]
        
        return min(dp)

[LeetCode] 265. Paint House II

 Problem : https://leetcode.com/problems/paint-house-ii/

A naive DP solution. 

Time complexity = O ( N * K * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            
            for j in range(K):
                for k in range(K):
                    if j != k:            
                        tmp[j] = min(tmp[j], costs[i][j] + dp[k])
            
            dp = tmp
        
        return min(dp)

Use extra space to find the minimal value of DP except position i. 

Time complexity  = O ( N * K )

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        N = len(costs)
        K = len(costs[0])
        MAX_INT = 2**31 - 1
        
        dp = costs[0]
        
        for i in range(1, N):
            tmp = [MAX_INT] * K
            leftMi = [MAX_INT] * K  # minimum value from left
            rightMi = [MAX_INT] * K # minimum value from right
            
            mi = dp[0]
            for j in range(1, K):
                leftMi[j] = mi
                mi = min(mi, dp[j])
            
            mi = dp[K-1]
            for j in reversed(range(K-1)):
                rightMi[j] = mi
                mi = min(mi, dp[j])
            
            for j in range(K):
                tmp[j] = min(leftMi[j], rightMi[j]) + costs[i][j]
            
            dp = tmp
        
        return min(dp)

[LeetCode] 926. Flip String to Monotone Increasing

 Problem : https://leetcode.com/problems/flip-string-to-monotone-increasing/

One valid monotone-increasing can either end by '0'  or '1'.

For every s[i], consider the number of flip may need by appending it to the monotone-increasing ended by flipping s[i-1].

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        N = len(s)
        
        end_by_zero = 0 if s[0] == '0' else 1
        end_by_one = 0 if s[1] == '1' else 0
        
        for i in range(1, N):
            if s[i] == '0':
                # no need to flip to expand valid monotone increasing end by 0
                # end_by_zero = end_by_zero
                
                # flip 0 to 1 to expand valid monotone increasing end by 1
                end_by_one = end_by_one + 1
            elif s[i] == '1':
                # no need to flip to expand valid monotone increasing end by 1
                end_by_one = min(end_by_zero, end_by_one)
                
                # flip 1 to 0 to expand valid monotone increasing end by 1
                end_by_zero = end_by_zero + 1         
        
        return min(end_by_zero, end_by_one)

[LeetCode] 276. Paint Fence

 Problem : https://leetcode.com/problems/paint-fence/

Similar to the climbing-stairs, we should think about the 'last state'.

When we paint the last fence, we either paint it with a different color or paint it with the same color as the last 2 fence.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_diff_color = [0] * n
        end_with_same_color = [0] * n
        
        end_with_diff_color[0] = k
        
        for i in range(1, n):
            end_with_diff_color[i] = end_with_same_color[i-1] * (k-1) + end_with_diff_color[i-1] * (k-1)
            end_with_same_color[i] = end_with_diff_color[i-1]
            
        return end_with_diff_color[-1] + end_with_same_color[-1]

Because "i" state only dependes on the result of "i - 1" state. We can reduce the space complexity.

class Solution:
    def numWays(self, n: int, k: int) -> int:
        end_with_same_color, end_with_diff_color = 0, k
    
        for i in range(1, n):
            end_with_same_color, end_with_diff_color = end_with_diff_color, end_with_same_color * (k-1) + end_with_diff_color * (k-1)
                        
        return end_with_diff_color + end_with_same_color

[LeetCode] 639. Decode Ways II

 Problem : https://leetcode.com/problems/decode-ways-ii/

The top-down solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        
        @cache
        def helper(start):
            """
            total decoding way of s[start:]
            """
            
            if start == len(s):
                return 1
            
            # '0' cannot be the leading digit
            if s[start] == '0':
                return 0
            
            # total decoding way when consider s[start] is a letter
            result = (9 if s[start] == '*' else 1) * helper(start + 1)
            
            # total decoding way when consider s[start]s[start+1] is a letter 
            if start + 1 < len(s):
                if s[start] == '1':
                    if s[start+1] != '*':
                        result += 1 * helper(start + 2)
                    else:
                        # s[start+1] == '*'
                        result += 9 * helper(start + 2)
                elif s[start] == '2':
                    if '0' <= s[start+1] <= '6':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += 6 * helper(start + 2)
                elif s[start] == '*':
                    if '0' <= s[start+1] <= '6':
                        result += 2 * helper(start + 2)
                    elif '7' <= s[start+1] <= '9':
                        result += 1 * helper(start + 2)
                    elif s[start+1] == '*':
                        result += (9 + 6) * helper(start+2)
            
            return result % (10 ** 9 + 7)
         
        return helper(0)

The bottom-up solution:

class Solution:
    def numDecodings(self, s: str) -> int:
        M = 10 ** 9 + 7
        N = len(s)
        
        if s[0] == '0': return 0
        
        dp = [0] * (N+1)
        dp[0] = 1
        dp[1] = 9 if s[0] == '*' else 1
        
        for i in range(1, N):
            if s[i] == '*':
                dp[i+1] = 9 * dp[i] % M
                
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + 9 * dp[i-1]) % M
                elif s[i-1] == '2':
                    dp[i+1] = (dp[i+1] + 6 * dp[i-1]) % M
                elif s[i-1] == '*':
                    dp[i+1] = (dp[i+1] + 15 * dp[i-1]) % M
            else:
                dp[i+1] = dp[i] if s[i] != '0' else 0
                if s[i-1] == '1':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '2' and s[i] <= '6':
                    dp[i+1] = (dp[i+1] + dp[i-1]) % M
                elif s[i-1] == '*':
                    if s[i] <= '6':
                        dp[i+1] = (dp[i+1] + 2 * dp[i-1]) % M
                    else:
                        dp[i+1] = (dp[i+1] + dp[i-1]) % M
        
        return dp[N]

[LeetCode] 1220. Count Vowels Permutation

 Problem : https://leetcode.com/problems/count-vowels-permutation/

In one state, we remember the number of permutations end by a particular vowel letter. Then the next state can be built upon the current state base on the given extending rule.

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels = {v: 1 for v in ['a', 'e', 'i', 'o', 'u']}
        
        for i in range(1, n):
            tmp = {}
            # extend permutations by appending 'a'
            tmp['a'] = vowels['e'] + vowels['u'] + vowels['i']
            # extend permutations by appending 'e'
            tmp['e'] = vowels['a'] + vowels['i']
            # extend permutations by appending 'i'
            tmp['i'] = vowels['e'] + vowels['o']
            # extend permutations by appending 'o'
            tmp['o'] = vowels['i']
            # extend permutations by appending 'u'
            tmp['u'] = vowels['o'] + vowels['i']
            # move to the next state
            vowels = tmp
        
        return sum(vowels.values()) % (10**9 + 7)

[LeetCode] 931. Minimum Falling Path Sum

 Problem : https://leetcode.com/problems/minimum-falling-path-sum/

A classic DP problem.

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        dp = matrix[0][:]
        tmp = [0] * COLUMN
        
        for y in range(1, ROW):
            for x in range(COLUMN):
                tmp[x] = dp[x]
                
                if x - 1 >= 0:
                    tmp[x] = min(tmp[x], dp[x-1])
                    
                if x + 1 < COLUMN:
                    tmp[x] = min(tmp[x], dp[x+1])
                
                tmp[x] += matrix[y][x]
            
            dp, tmp = tmp, dp
        
        return min(dp)

[LeetCode] 377. Combination Sum IV

 Problem : https://leetcode.com/problems/combination-sum-iv/

This quiz is similar to "Coin Change". 

Assume taking nums[i], find the combination for sum = target - nums[i].

Time complexity = O ( M * N ). M = target, N = len(nums)

Top-down solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        
        @lru_cache(maxsize = None)
        def helper(remain):
            if remain == 0: return 1
            
            result = 0
            
            for i in range(N):
                if nums[i] <= remain:
                    result += helper(remain - nums[i])
                else:
                    break
            
            return result

        return helper(target)

Bottom-up solution:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        
        nums.sort()
        
        for combo in range(1, target+1):
            for n in nums:
                if n > combo:
                    break
                    
                dp[combo] += dp[combo - n]
        
        return dp[target]

Follow-up question:

To allow negative number in the given array, we need to limit the ouput combination length. Otherwise, it won't be able to stop the searching.

[LeetCode] 376. Wiggle Subsequence

 Problem : https://leetcode.com/problems/wiggle-subsequence/

Intuitive DP solution:

dp[i][0] = length of the longest up-wiggle sequence ends by i-th number

dp[i][1] = length of the longest down-wiggle sequence ends by i-th number

Update dp[i][0] and dp[i][1] by comparing nums[i] with all numbers before it.

Time complexity = O ( N ** 2 )

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        
        if N < 2: return N
        
        dp = [[0, 0] for _ in range(N)]
        dp[0][0] = dp[0][1] = 1
        
        result = 0
        
        for i in range(N):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)
                elif nums[i] < nums[j]:
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)
            
            result = max(result, dp[i][0], dp[i][1])
        
        return result

Linear DP solution:

up[i] = length of the longest up-wiggle sequence in section nums[0:i+1].

down[i] = length of the longest down-wiggle sequence in section nums[0:i+1]

Be aware, the longest up / down wiggle sequence is not necessary ends by nums[i].

For every nums[i], there could be 3 cases:

When nums[i] == nums[i-1]: 

nums[i] cannot extend either previous up-wiggle or down-wiggle sequence,

up[i] = up[i-1], down[i] = down[i-1]

When nums[i] < nums[i-1]:

nums[i] can be appended to previous down-wiggle sequence  and create a longer up-wiggle sequence, up[i] = down[i-1] + 1

nums[i] cannot be appended to previous up-wiggle sequence to create a longer down-wiggle sequence.

So, length of the longest down-wiggle sequence in section nums[0:i+1] does not change.

down[i] = down[i-1]

When nums[i] > nums[i-1]:

nums[i] can be appended to previous up-wiggle sequence and create a longer down-wiggle sequence,

down[i] = up[i-1] + 1

nums[i] cannot be appended to previous down-wiggle sequence to create a longer up-wiggle sequence.

So, length of the longest up-wiggle sequence in section nums[0:i+1] does not change.

up[i] = up[i-1]

Time Complexity = O ( N )

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        
        if N < 2: return N
        
        up = [0] * N
        down = [0] * N
        
        up[0] = down[0] = 1
        
        for i in range(1, N):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1]
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]
        
        return max(up[-1], down[-1])

Because for i-th number, it only compares the previous number to update the up / down wiggle sequence of section nums[0:i+1].

It only needs 2 variables to the save the length of up-wiggle and down-wiggle sequence of section nums[0:i]

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        
        if N < 2: return N

        up = down = 1
        
        for i in range(1, N):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1

        return max(up, down)

[LeetCode] 368. Largest Divisible Subset

 Problem : https://leetcode.com/problems/largest-divisible-subset/

For a valid subset in ascending order [A, B, C, D], if the largest number D can be divided by the Number e, then the subset [A, B, C, D, e] is still a valid subset.

Time Complexity = O ( N ** 2)

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
      int N = nums.length;

      // Maximum length of valid subset ends by the ith number,
      int[] count = new int[N];
      // Index of previous number, to which the ith number can be appended, to form the longest subset.
      int[] pre = new int[N];
      

      int maxSoFar = 0;
      int index = 0;

      Arrays.sort(nums);
      
      for (int i = 0; i < N; i++) {
        pre[i] = -1;
        count[i] = 1;
        for (int j = i - 1; j >= 0; j--) {
          if (nums[i] % nums[j] == 0) {
            // If nums[i] can be divided by nums[j], we can expend the subset ends by nums[j]
            // Because all nums[j] can be divided by all other numbers in the subset,
            // nums[i] can also be divided by other numbers in the current subset.
      
            // No need to update count[i], if nums[i] can form a longer subset with other number.
            if (count[j] + 1 > count[i]) {
              count[i] = count[j] + 1;
              pre[i] = j;
            
              if (maxSoFar < count[i]) {
                index = i;
                maxSoFar = count[i];
              }
            }
          }
        }
      }

      // Start from the last number of the longest subset and
      // iterate back to the beginner ( pre[index] == -1)
      LinkedList<Integer> result = new LinkedList<>();
      while (index != -1) {
        result.offerFirst(nums[index]);
        index = pre[index];
      }

      return result;
    }
}
        

Edited on: 04/06/2025. Add detail explanation to the steps.

[LeetCode] 354. Russian Doll Envelopes

 Problem : https://leetcode.com/problems/russian-doll-envelopes/

This problem equals to find the length of longest increasing subsequence on 2 dimensions.

1. Sort the array. Ascending on width and descend on height for same width.

Because [3,3] cannot be contained by [3, 4], we need to put [3,4] in front of [3,3]. Otherwise,  "[3,3], [3,4]" will be considered as a valid increasing subsequence.

2.  Find the longest increasing subsequence base on height.

Since width of envelop has been sorted in increasing order, we only need to consider height.

Time Complexity = O ( N Log N )

from functools import cmp_to_key

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        
        def lowerBound(dp, n):
            left, right = 0, len(dp)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if dp[mid] == n:
                    right = mid
                elif dp[mid] > n:
                    right = mid
                elif dp[mid] < n:
                    left = mid + 1
            
            return left
        
        def compare(a, b):
            return a[0] - b[0] if a[0] != b[0] else b[1] - a[1]
        
        envelopes.sort(key=cmp_to_key(compare))
        
        dp = []
        
        for _, h  in envelopes:
            i = lowerBound(dp, h)
            
            if i == len(dp):
                dp.append(h)
            else:
                dp[i] = h
        
        return len(dp)

[LeetCode] 343. Integer Break

 Problem : https://leetcode.com/problems/integer-break/

For each number i,  it can be broken into at least  j,  (i-j).  j = [1 ... i -1]

Let DP[i] = maximum product of number i when i be broken into at least 2 integers.

DP[i] = Max( j * (i-j),  j * DP[i-j] ),    j = [ 1 ... i - 1 ]

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], max(j* (i-j),  j *dp[i-j]))
        
        return dp[n]

Another memorization approach:

class Solution {
    int[] memo;
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        memo[1] = 1;
        
        return helper(n);
    }
    
    int helper(int n) {
        if (memo[n] != 0) {
            return memo[n];
        }
        
        for (int x = 1; x <= n / 2; x++) {
            
            // i.e. For number 3,  helper(3) = 1 * 2 = 2. 
            // 3 > helper(3).  we need to use 3 instead of helper(3) to get the larger product.
            memo[n] = Math.max(memo[n], Math.max(x, helper(x)) * Math.max(n-x, helper(n-x)));
        } 
        
        return memo[n];
    }
}

Edited on 11/26/2021. Update the top-down solution.