Optimising Dynamic Programming Approach for Painter’s Problem using Precomputation
The time complexity of the above program is O(k∗N3). It can be easily brought down to O(k∗N2) by pre-computing the cumulative sums in an array, thus avoiding repeated calls to the sum function.
Below is the how we can achieve this optimisation:
C++
int sum[n + 1] = { 0 };// sum from 1 to i elements of arrfor (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i - 1];for (int i = 1; i <= n; i++) dp[1][i] = sum[i];// and using it to calculate the result as:best = min(best, max(dp[i - 1][p], sum[j] - sum[p])); |
Java
int sum[] = new int[n + 1];// sum from 1 to i elements of arrfor (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i - 1];for (int i = 1; i <= n; i++) dp[1][i] = sum[i];// and using it to calculate the result as:best = Math.min(best, Math.max(dp[i - 1][p], sum[j] - sum[p]));// This code is contributed by divyesh072019. |
Python3
sum = [0] * (n + 1)# sum from 1 to i elements of arrfor i in range(1, n + 1): sum[i] = sum[i-1] + arr[i-1]for i in range(1, n + 1): dp[1][i] = sum[i]# and using it to calculate the result as:best = min(best, max(dp[i-1][p], sum[j] - sum[p]))# This code is contributed by kraanzu. |
C#
int[] sum = new int[n + 1];// sum from 1 to i elements of arrfor (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i - 1];for (int i = 1; i <= n; i++) dp[1, i] = sum[i];// and using it to calculate the result as:best = Math.Min(best, Math.Max(dp[i - 1][p], sum[j] - sum[p]));// This code is contributed by divyeshrabadiya07. |
Javascript
<script>let sum = new Array(n+1); // sum from 1 to i elements of arrfor (let i = 1; i <= n; i++) sum[i] = sum[i-1] + arr[i-1]; for (let i = 1; i <= n; i++) dp[1][i] = sum[i]; // and using it to calculate the result as:best = Math.min(best, Math.max(dp[i-1][p], sum[j] - sum[p]));// This code is contributed by Saurabh Jaiswal.</script> |
Note: Though here we consider dividing A into k or fewer partitions, we can observe that the optimal case always occurs when we divide A into exactly k partitions.
So we can use:
C++
for (int i = k - 1; i <= n; i++) best = min(best, max(partition(arr, i, k - 1), sum(arr, i, n - 1))); |
Java
for (int i = k - 1; i <= n; i++) best = Math.min(best, Math.max(partition(arr, i, k - 1), sum(arr, i, n - 1)));// This code is contributed by pratham76. |
Python3
for i range(k-1, n+1): best = min(best, max(partition(arr, i, k-1), sum(arr, i, n-1)))# This code is contributed by Aman Kumar. |
C#
for (int i = k - 1; i <= n; i++) best = Math.Min(best, Math.Max(partition(arr, i, k - 1), sum(arr, i, n - 1)));// This code is contributed by rutvik_56 |
Javascript
for(var i = k - 1; i <= n; i++) best = Math.min(best, Math.max(partition(arr, i, k - 1), sum(arr, i, n - 1))); // This code is contributed by Ankita saini |
Exercise:
Can you come up with a solution to this Painter’s Problem using Binary Search?
The Painter’s Partition Problem
Given are N boards of with length of each given in the form of array, and K painters, such that each painter takes 1 unit of time to paint 1 unit of the board. The task is to find the minimum time to paint all boards under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.
Examples:
Input: N = 4, A = {10, 10, 10, 10}, K = 2
Output : 20
Explanation: Here we can divide the boards into 2 equal sized partitions (Painter 1 will paint boards A1 and A2, and Painter 2 will paint boards A3 and A4). So each painter gets 20 units of board and the total time taken is 20.
Input: N = 4, A = {10, 20, 30, 40}, K = 2
Output : 60
Explanation: Since there are only 2 painters, therefore divide first 3 boards to painter 1 (A1, A2 and A3) with time = 60, and last board to painter 2 (A4) with time = 40. Therefore total time taken = 60, which is the minimum possible.
Please note the combination A1 and A4 to Painter 1 with time 50, and A2 and A3 to Painter 2 with time 50, will yield a smaller time (50 units). But this cant be considered due to the constraint that a painter cannot paint non-continuos series of boards.