2
$\begingroup$

I am trying to do the leetcode question

I got the answer and trying to understand a systematical way to come up with the answer using the DP bottom-up approach, and I am having a hard time to understand it, up to m=2.

  1. What would be the best way to visualized or step by step to come up with this answer??
  2. What is non-after effect property?

The problem statement:

"Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays."

Example to clarify the Question

Given the array [7,2,5,10,8] and split it into 2, there are 4 possible ways to split the array, with a minimum of 1 element in a subarray:

  • [7][2,5,10,8] , largestSum 25 = sum(2,5,10,8)

  • [7,2][5,10,8] , largestSum 23 = sum(5,10,8)

  • [7,2,5][10,8] , largestSum 18 = sum(10,8)

  • [7,2,5,10][8] , largestSum 24 = sum(7,2,5,10)

    min(largestSums) = 18

Intuition

The problem satisfies the non-aftereffect property. We can try to use dynamic programming to solve it.

The non-aftereffect property means, once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting nums[0..i] into j parts, this value will not be affected by how we split the remaining part of nums.

To know more about non-aftereffect property, this link may be helpful : http://www.programering.com/a/MDOzUzMwATM.html

Basic idea

  • row is referring to the partition size
  • col is referring to the array nums

**Visualized **

     7, 2, 5,10, 8
0[0, ∞, ∞, ∞, ∞, ∞]
1[∞, ∞, ∞, ∞, ∞, ∞]
2[∞, ∞, ∞, ∞, ∞, ∞]
3[∞, ∞, ∞, ∞, ∞, ∞]

Here is the working code and output

$\endgroup$
  • 2
    $\begingroup$ Please edit your question to summarize the solution you are trying to understand, to make your question self-contained. We don't want people to have to click on a link to understand your question, and we want the question to remain intelligible even if the link stops working. Don't use code, but describe the algorithm with concise pseudocode. If all you have is code and you want to understand how the code works, that question is probably off-topic here, as questions about code are outside of our scope. $\endgroup$ – D.W. Nov 6 '19 at 0:23
  • $\begingroup$ What programming paradigms have you tried? Have you tried dynamic programming? Are you familiar with it? I recommend you study the material linked here: cs.stackexchange.com/tags/dynamic-programming/info, and/or a good textbook on the subject. $\endgroup$ – D.W. Nov 6 '19 at 0:24
  • $\begingroup$ @D.W. I am using DP, bottom-up approach. $\endgroup$ – Jaxox Nov 7 '19 at 3:20
  • $\begingroup$ The questions at the link I posted give a systematic way to come up with a dynamic programming algorithm. $\endgroup$ – D.W. Nov 7 '19 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.