Ninja Training

A ninja has planned a n-day training schedule. Each day he has to perform one of three activities - running, stealth training, or fighting practice. The same activity cannot be done on two consecutive days and the ninja earns a specific number of merit points, based on the activity and the given day.

Given a n x 3-sized matrix, where matrix[i][0], matrix[i][1], and matrix[i][2], represent the merit points associated with running, stealth and fighting practice, on the (i+1)th day respectively. Return the maximum possible merit points that the ninja can earn.

Examples:
// Input: matrix = [[10, 40, 70], [20, 50, 80], [30, 60, 90]]
// Output: 210
// Explanation:
// Day 1: fighting practice = 70
// Day 2: stealth training = 50
// Day 3: fighting practice = 90
// Total = 70 + 50 + 90 = 210
// This gives the optimal points.

// Memoization - O(n*4*3) time and O(n*4)+O(n) space
class Solution
{
public:
    int func(vector<vector<int>> &matrix, vector<vector<int>> &dp, int day, int last)
    {
        if (day == 0)
        {
            int maxPoints = 0;
            for (int i = 0; i < 3; i++)
            {
                if (i != last)
                {
                    maxPoints = max(maxPoints, matrix[day][i]);
                }
            }
            return dp[day][last] = maxPoints;
        }
        if (dp[day][last] != -1)
            return dp[day][last];

        int maxPoints = 0;
        for (int i = 0; i < 3; i++)
        {
            if (i != last)
            {
                int points = matrix[day][i] + func(matrix, dp, day - 1, i);
                maxPoints = max(maxPoints, points);
            }
        }
        return dp[day][last] = maxPoints;
    }
    int ninjaTraining(vector<vector<int>> &matrix)
    {
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(4, -1));

        return func(matrix, dp, n - 1, 3);
    }
};

// Tabulation - O(n*4*3) time and O(n*4) space

class Solution2
{
public:
    int ninjaTraining(vector<vector<int>> &matrix)
    {
        int n = matrix.size();
        vector<vector<int>> dp(n, vector<int>(4, -1));
        dp[0][0] = max(matrix[0][1], matrix[0][2]);
        dp[0][1] = max(matrix[0][0], matrix[0][2]);
        dp[0][2] = max(matrix[0][0], matrix[0][1]);
        dp[0][3] = max(matrix[0][0], max(matrix[0][1], matrix[0][2]));

        for (int day = 1; day < n; day++)
        {
            for (int last = 0; last < 4; last++)
            {
                dp[day][last] = 0;
                for (int task = 0; task < 3; task++)
                {
                    if (task != last)
                    {
                        int points = matrix[day][task] + dp[day - 1][task];
                        dp[day][last] = max(dp[day][last], points);
                    }
                }
            }
        }

        return dp[n - 1][3];
    }
};

// Space Optimization - only previous day is required to calculate current day. O(n*4*3) time and O(4) space

class Solution
{
public:
    int ninjaTraining(vector<vector<int>> &matrix)
    {
        int n = matrix.size();

        vector<int> prev(4, 0);

        prev[0] = max(matrix[0][1], matrix[0][2]);
        prev[1] = max(matrix[0][0], matrix[0][2]);
        prev[2] = max(matrix[0][0], matrix[0][1]);
        prev[3] = max(matrix[0][0], max(matrix[0][1], matrix[0][2]));

        for (int day = 1; day < n; day++)
        {
            vector<int> temp(4, 0);
            for (int last = 0; last < 4; last++)
            {
                temp[last] = 0;
                for (int task = 0; task <= 2; task++)
                {
                    if (task != last)
                    {
                        temp[last] = max(temp[last], matrix[day][task] + prev[task]);
                    }
                }
            }
            prev = temp;
        }

        return prev[3];
    }
};

Count all Possible Routes

You are given an array of distinct positive integers locations where locations[i] represents the position of city i. You are also given integers start, finish and fuel representing the starting city, ending city, and the initial amount of fuel you have, respectively.

At each step, if you are at city i, you can pick any city j such that j != i and 0 <= j < locations.length and move to city j. Moving from city i to city j reduces the amount of fuel you have by |locations[i] - locations[j]|. Please notice that |x| denotes the absolute value of x.

Notice that fuel cannot become negative at any point in time, and that you are allowed to visit any city more than once (including start and finish).

Return the count of all possible routes from start to finish. Since the answer may be too large, return it modulo 10^9 + 7.

Example:

// Input: locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
// Output: 4
// Explanation: The following are all possible routes, each uses 5 units of fuel:
// 1 -> 3
// 1 -> 2 -> 3
// 1 -> 4 -> 3
// 1 -> 4 -> 2 -> 3

int mod = 1e9 + 7;
    int n;
    int func(vector<int> &locations, vector<vector<int>> &dp, int i, int &finish, 
             int &fuel)
    {
        if (fuel < 0)
            return 0;
        if (dp[i][fuel] != -1)
            return dp[i][fuel];

        int ans = 0;
        if (i == finish)
            ans += 1;

        for (int j = 0; j < n; j++)
        {
            if (i == j)
                continue;
            int fuelLeft = fuel - abs(locations[i] - locations[j]);
            ans = (ans + func(locations, dp, j, finish, fuelLeft)) % mod;
        }
        return dp[i][fuel] = ans;
    }
    int countRoutes(vector<int> &locations, int start, int finish, int fuel)
    {
        n = locations.size();
        vector<vector<int>> dp(n, vector<int>(fuel + 1, -1));
        return func(locations, dp, start, finish, fuel);
    }