2020 Jan Silver Problem 1 Berry Picking

Official Problem Statement

Berry Picking

Problem Statement:

Berry Picking

Farmer John has a large berry field, consisting of N (1 ≤ N ≤ 10,000) rows of berries, numbered 1..N from north to south. Each row contains M (1 ≤ M ≤ 10,000) columns of berries, numbered 1..M from east to west.

Farmer John wants to pick some berries. He starts at the northernmost row and wants to pick some berries from each row, moving southward. In each row, he will pick a contiguous range of columns.

Solution:

The solution to this problem is to use a dynamic programming approach. We can create a two-dimensional array, dp[i][j], which stores the maximum number of berries that can be picked from the first i rows, ending at column j. We can then fill in the array using the following recurrence:

dp[i][j] = max(dp[i-1][k] + sum(berries from columns k+1 to j))

where k ranges from 0 to j.

The code for this solution in C++ is as follows:

int dp[N+1][M+1];

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        dp[i][j] = 0;
        for (int k = 0; k < j; k++) {
            dp[i][j] = max(dp[i][j], dp[i-1][k] + sum(berries from columns k+1 to j));
        }
    }
}