Hi guys. I just tried to solve the recent ICPC Singapore problem G with DP bottom up. The summary of description is like this :
Given sequence with length N < 3000 with each in range 1 and 109. Find the maximum partition can be made with each sum of partition elements cannot bigger than sum of elements on the right partition
My answer is by make table DP[i, j] contains maximum partition can be made from element [1, j] with last partition covers [i, j]. And then fill the table with DP[i, j] = max{DP[k, i - 1]} + 1 if only Sumk, i - 1 ≤ Sumi, j
Are there any flaws with my approach?
int -> long long
Initialize dpp to - ∞. With dpp=0 you might be considering partitions of some subarray of the original array, like [2..3], [4..5] for the subarray [2..5], when you really have to partition the whole array.
Counter test:
Sorry, but can you explain a bit why dpp=0 is wrong? I still dont understand
If you can't find some valid partition ending at i - 1, you are simply considering you can start a new partition from i, ignoring all previous elements. For example, in the countertest above you are ignoring briefcase 1 in your optimal solution, when you have to use it. That's because your default value of dpp=0 and dp[2][_] will be 0 (1-indexed), which is not correct, since there's no valid partition to it's left. Then when you get to dp[3][], you will make a invalid 1-partition using previous value of dp[2][].