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 [1, i - 1]. 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?
