Leetcode diary: 983. Minimum Cost For Tickets

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question is hard for me for some reason. I don't think this particular problem is that much more difficult than the others that I have done, but there is just something not clicking not quite right. Follow me on this journey of shooting myself in the foot over and over :D

Given the costs of 1 day, 7 days, and 30 days pass, find the minimum cost to travel on all the days given in an array. Each day is represented by an integer, so we will have 1-365 (this constraint is kinda important).

The overall goal of the problem solution is to find how many days we can use the pass effectively. By effectively, it is that pass a certain number of days, it is cheaper to buy the pass. For example if the costs are [oneDay, weekly, monthly] = [2,7,30], then there are conditions when weekly or monthly is preferable than one day passes. In this particular set up, once you have 4 or more days in a week, then it is more effective to buy the weekly pass. Keep this in mind while solving this problem, we are to mimic this behavior programmatically somehow.

The first thing we can do is the brute force as per usual:

var mincostTickets = function(days, costs) {
    const [single, weekly, monthly] = costs;
    let min = Number.MAX_SAFE_INTEGER;
    recurr(0, 0);
    return min

    function recurr(index, cost) {
        if(index > days.length-1) {
            min = Math.min(min, cost)
            return;
        };

        handleMonthlyWeekly  (index, cost + monthly, 29)
        handleMonthlyWeekly  (index, cost + weekly, 6)
        recurr(index+1, cost + single)
    }


    function handleMonthlyWeekly (index, cost, addedDays) {
        const currentDay = days[index];
        const lastValidDay = currentDay + addedDays;

        let current = days[++index];

        while (lastValidDay >= current && current !== undefined) {
            current = days[++index];
        }

        recurr(index, cost)
    }
};

the set up of the code is relatively easy to understand, we get the cost of each pass type in an easily accessible variable, then we initialize the "min" variable to be changed in the recurr() and just return the min from the end.
The recurr() record the cost whenever the recursion reaches beyond the last day in the days[]. If it hasn't reached yet, then it'll branch out in monthly, weekly, and single day so that we can get all the possible permutations for this problem.
handleMonthlyWeekly() all it does is skip all the days the the pass covers and calls recurr with the next travel day index.

The obvious problem is that the call stack is huge and we are potentially doing repeated work. So we need to memoize something.

This where my current solution presents a big problem, it does not allow for anything to be potentially stored. This is because there is only the concept of branching out, but no concept of recording the result of each step.

This is where I basically stumbles into the depths of hell, so let's look at a similar solution with memoization:

var mincostTickets = function(days, costs) {
    const [one, seven, thirty] = costs;
    const memo = new Map()

    function recurse(curr, idx) {
        if(memo.has(curr)) return memo.get(curr);
        if(idx >= days.length) return 0;
        if(curr >= days[idx]) return recurse(curr, idx+1);

        const buy1 = recurse(days[idx], idx) + one;
        const buy7 = recurse(days[idx]+6, idx) + seven;
        const buy30 = recurse(days[idx]+29, idx) + thirty;
        const min = Math.min(buy1, buy7, buy30);
        memo.set(curr, min);
        return min;
    }
    return recurse(0, 0);
};

The approach is relatively similar. We both start at 0, and the DFS will branch out accordingly until the index overreaches. I find it cleaver that he simply solves the "days covered by the pass" in
if(curr >= days[idx]) return recurse(curr, idx+1);.

The major change here is that he records the minimum of each recursion and returns that minimum if re-encountered. This is the basic concept of DP. However, the thing that trips me up is that how do you know that it is the true minimum you are recording ? Because the code does not change the memo map, it simply returns the map value when re-encountered, so the record MUST be the minimum.

I think this is where the problem with this solution appears, it is kind of hard to follow what is happening with the curr and idx variable. The idx variable is the pointer to the days[], it is the current index, aptly named. Curr, however, is the current day the recursion is on. So this is a separate concept from the numbers in the days[]. Note that we are also memoizing on the curr variable too.
So the way this solutions works is via looking at a time line from day 1 to n, where n is the last day in days[]. The record then records the minimum cost not accounting for the day of. You'll probably have to see this in the console log to understand, but for days 13,12,11 in the memo, it's all 2, because they account for the travel on 20th. For day 7, it accounts for 8th and 20th, but not on the day itself, so it is 4.

Note that because of
if(curr >= days[idx]) return recurse(curr, idx+1);.
it means that we aren't recording literally every single day possible. Note that also curr is set via variables like:
days[idx]+6, so we curr isn't a continuous integer from 1 to n.

Now the tricky part is that since it's a DFS, we are actually recording backwards from the last day to the first day, and we are returning the cost on day 0. This should be an expected caveat for those familiar with DFS.
The problem now is how does it mimic the "switch over to weekly/monthly pass" behavior that our brains can do?
in the test case of:
[1,4,6,7,8,20]
[2,7,15]
This happens on day 1. Let's work backwards first:
day 20 = $0: because no travel day after it
day 8 = $2: only 20th after
day 7 = $4: 8th and 20th after
day 6 = $6: 7th, 8th, and 20th after
day 4 = $8: 6th, 7th, 8th, and 20th after
day 1 = $9:
4th, 6th, 7th, 8th, this sequence no longer makes sense to buy 1 day pass individually, so we'll do a weekly here. How the code does this is that it does Math.min on the possibilities. The 30 day pass is 15, as it is throughout the entire run of program. The 1 day pass is 2 * 5 = 10, the 7 days pass is 7 + 2 = 9.
It's worth understanding how the 9 come from. We are at day 1, so we actually care about 4th - 20th day. The code first does:
const buy7 = recurse(days[idx]+6, idx) + seven;

idx = 1 so days[idx] = 4+6 = 10.
when the recursion is at 10, it'll do:
if(curr >= days[idx]) return recurse(curr, idx+1);

until idx = 5, at which point the code will branch out for buy1, buy7, and buy30.
buy1 will make curr = days[idx] = 20. This will get idx incremented one more time to be equal days.length, and the recursion will return 0. Thus, buy1 = 0 + 2 = 2. buy7 and buy30 will similarly follow and be 7 and 15 each, the min of 2,7,15 is 2.
Therefore recurse(days[idx]+6, idx) = 2, + seven = 9. So we get day1 = 9.

This process repeats for day 0, except that the memo has day 7 so the code returns 4 and add 7 immediately for the buy7 variable.

I think I know what my problem is, it is that there was one problem, dang I can't remember which, that we cannot do greedy algorithm for. This means that if it is true for this problem, then we can't memoize and assume that for day 7, 4 is its absolute minimal cost. I think having this at the back of the mind fucked with me real hard on this problem. Would be great if someone can provide an example/explanation for when such assumption is not possible.

I want to leave you with the best solution below:

function dp (days, costs) {
    const dp = Array(days[days.length - 1] + 1).fill(0);
    const [cost1Day, cost7Day, cost30Day] = costs;

    for (let d of days) {
        dp[d] = 1;
    }

    for (let i = 1; i <= days[days.length - 1]; i++) {
        if (dp[i]) {
            dp[i] = Math.min(cost1Day + dp[i - 1], cost7Day + dp[Math.max(0, i - 7)], cost30Day + dp[Math.max(0, i - 30)]);
        } else {
            dp[i] = dp[i - 1];
        }
    }

    return dp.pop();
}

What differs this solution from the previous is that it realizes that what we are doing with the DFS is adding in travel days one by one and figure out the least cost in each subsequence. So instead doing all of that mess via recursion, why not just go forward sequentially and just build the result via subsequence growth too?

I think this question is exhausted, I'll come back soon with another similar problem.

Let me know anything on your mind after reading through this, THANKS!