Vacation

Note: This problem is part of the Atcoder Educational Dp Contest

Problem Link

Brute-Force/Recursive Approach

We know that we cannot take any given activity for two or more days in a row. So our decision to choose an activity will depend on what our previous decisions were: we will pass two parameters in our recursive function: i and j. Here, i denotes the ith day and j denotes the activity choosen on the i+1th day (0->A, 1->B, 2->C). Our basic logic is: we will only consider activities on the ith day that doesn’t equal j because we already chose that on the next day. Therefore, the maximum points we can gain is by choosing one of the two remaining activities for the ith day plus the profit from the previous days (recursively).

Code

#include <bits/stdc++.h>
using namespace std;

int recursive(vector<vector<int>> &act, int i, int j)
{
    int res = 0;
    if (i < 0)
        return res;
    if (i == 0)
    {
        for (int a = 0; a <= 2; ++a)
        {
            if (a == j) continue;
            res = max(res, act[a][0]);
        }
        return res;
    }
    
    for (int a = 0; a <= 2; ++a)
    {
        if (a == j) continue;
        res = max(res, act[a][i] + recursive(act, i - 1, a));
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> act(3, vector<int>(n));
    for (int i = 0; i < n; ++i)
        cin >> act[0][i] >> act[1][i] >> act[2][i];

    cout << max({recursive(act, n - 2, 0) + act[0][n - 1],
                 recursive(act, n - 2, 1) + act[1][n - 1],
                 recursive(act, n - 2, 2) + act[2][n - 1]});
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(2^n)}$ - Size of recursion tree will be $2^n$
• Space complexity: $\boldsymbol{O(n)}$ - The depth of the recursion tree can go up to $n$.

Recursive (Top-down) + Memoization

Here, we cache the results of the recursive brute-force approach to reduce time complexity:

Code

#include <bits/stdc++.h>
using namespace std;

int n;
int topdown(vector<vector<int>> &act, int i, int j)
{
    static vector<vector<int>> dp(3, vector<int>(n, -1));
    if(dp[j][i] != -1) return dp[j][i];
    int res = 0;
    if (i < 0) return dp[j][i] = res;
    if (i == 0)
    {
        for (int a = 0; a <= 2; ++a)
        {
            if (a == j) continue;
            res = max(res, act[a][0]);
        }
        return dp[j][i] = res;
    }

    for (int a = 0; a <= 2; ++a)
    {
        if (a == j) continue;
        res = max(res, act[a][i] + topdown(act, i - 1, a));
    }
    return dp[j][i] = res;
}

int main()
{
    cin >> n;
    vector<vector<int>> act(3, vector<int>(n));
    for (int i = 0; i < n; ++i)
        cin >> act[0][i] >> act[1][i] >> act[2][i];

    cout << max({topdown(act, n - 2, 0) + act[0][n - 1],
                 topdown(act, n - 2, 1) + act[1][n - 1],
                 topdown(act, n - 2, 2) + act[2][n - 1]});
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(n)}$ - This is because the recursive function will only branch or call other recursive functions if it hasn’t cached the query yet. The number of possible calls is $n$ (We have to explore each stone)

• Space complexity: $\boldsymbol{O(n)}$ - We are caching $n$ results in our DP array and size of recursive stack is also at worst $n$.

Bottom-Up (Tabular)

From the recurrence relation, we can come up with the bottom up approach:

Base cases:
if (i < 0)
	return dp[j][i] = 0;
if (i == 0)
{
	for (int a = 0; a <= 2; ++a)
	{
		if (a == j) continue;
		dp[j][i] = max(dp[j][i], act[a][0]);
	}
	return dp[j][i];
}

Recurrence Relation:

for (int a = 0; a <= 2; ++a)
{
	if (a == j) continue;
	dp[j][i] = max(dp[j][i], act[a][i] + topdown(act, i - 1, a));
}
return dp[j][i];

Code

#include <bits/stdc++.h>
using namespace std;

int n;
int bottomup(vector<vector<int>> &act)
{
    vector<vector<int>> dp(3, vector<int>(n + 1));

    for (int i = 1; i <= n; ++i)
    {
        int a = act[0][i-1], b = act[1][i-1], c = act[2][i-1];
        dp[0][i] = max(dp[1][i - 1] + b,
                        dp[2][i - 1] + c);
        dp[1][i] = max(dp[0][i - 1] + a,
                        dp[2][i - 1] + c);
        dp[2][i] = max(dp[0][i - 1] + a,
                        dp[1][i - 1] + b);
    }
    return max({dp[0][n], dp[1][n], dp[2][n]});
}
 
int main()
{
    cin >> n;
    vector<vector<int>> act(3, vector<int>(n));
    for (int i = 0; i < n; ++i)
        cin >> act[0][i] >> act[1][i] >> act[2][i];
        
    cout << bottomup(act);
    return 0;
}

Complexity Analysis

• Time complexity: $\boldsymbol{O(n)}$ - We have single for loop that run in total of $n$ times.
• Space complexity: $\boldsymbol{O(n)}$ - We are caching $n$ results in our DP array.