Leetcode 403 Frog Jump(Optimised Approaches + Analysis & Triggers for EXC & INC DP VS JUMP DP)

class Solution {
public:
//unoptimal way to find if the next stone or not O(N)
    int stoneExist(int stone, vector<int> &stones){
        for(int i = 0; i < stones.size(); i++){
            if(stones[i] == stone){
                return i;
            }
        }
        return -1;
    }

 //optimal way to find if the next stone exist or not O(log(n))
    int stoneExistBS(int currentStoneIdx, int nextStone, vector<int> &stones){
        int l = currentStoneIdx + 1, r = stones.size() - 1, mid = -1;
        // cout << "Stone: " << stones[currentStoneIdx] << " Next Stone: " << nextStone << '\n';
        while(l <= r){
            int mid = (l + r) / 2;
            // cout << "mid: " << stones[mid] << '\n';
            if(stones[mid] == nextStone){
                return mid;
            }
            else if(stones[mid] > nextStone){
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }

    return -1;
    }

    long long getMinSteps(int level, int lastJump, vector<int> &stones, vector<vector<int> > &memo){
        // cout << path << '\n';
        if(level == stones.size() - 1){
            return 0;
        }
        if(memo[level][lastJump] != -1){
            return memo[level][lastJump];
        }
        //levels = stones
        //options = k - 1, k , k + 1
        //invalid k = 0
        //jump only if the stone exist
        long long minSteps = INT_MAX;
        for(int i = -1; i < 2; i++){
            int jump = lastJump + (int) i;
            if(jump > 0){
                int nextStoneIdx = stoneExistBS(level, stones[level] + jump, stones);
                //The next stone where we jump from current stone exist
                if(nextStoneIdx != -1){
                    minSteps = min(minSteps, 1 + getMinSteps(nextStoneIdx, jump, stones, memo));
                }
            }
        }
        return memo[level][lastJump] = minSteps;
    }


    bool isPossibleToReach(int level, int lastJump, vector<int> &stones, vector<vector<int> > &memo){
        if(level == stones.size() - 1){
            return true;
        }
        if(memo[level][lastJump] != -1){
            return memo[level][lastJump];
        }
        //levels = stones
        //options = k - 1, k , k + 1
        //invalid k = 0
        //jump only if the stone exist
        bool possible = false;
        for(int i = -1; i < 2; i++){
            int jump = lastJump + (int) i;
            if(jump > 0){
                int nextStoneIdx = stoneExistBS(level, stones[level] + jump, stones);
                //The next stone where we jump from current stone exist
                if(nextStoneIdx != -1){
                    possible |= isPossibleToReach(nextStoneIdx, jump, stones, memo);
                }
            }
        }
        return memo[level][lastJump] = possible;
    }

//USE unordered_map<int, int> => map<stone, stoneidx>
    //don't BS, just see if it exist in map, if it does move to the stone
    //For this specific question, optimal way to find if the stone exist or not can be done via storing all mapping of stone and their indexes in map
    //O(1) time
    //It is not possible to use MAPS in exclusion/inclusion dp(where generally the next level becomes invalid) or the extension of inclusion/exclusion dp, i.e. the JUMP DP(projects, job scheduling), because there we don't try to find the exact match of something. We look for some VALID level, and if we jump to that VALID level it won't violate the property/constraint defined over the problem.

/*
INCLUSION / EXCLUSION DP - GENERALLY it depends on what action we took on JUST PREVIOUS level. So an integer is maintained which has very few states.
For example in 0/1 binary strings or house robber , that states possible of the JUST PREVIOUS LEVEL are 2 => {0, 1} (last element 0 or not)/(last house robbed or not)
In PAINT HOUSE or GEEKS TRAINING, there can be more than 2 states, but OFTEN LIMITED, states possible are 3 => {0, 1, 2}
PAINT HOUSE = JUST PREVIOUS HOUSE painted RED(0), GREEN(1), BLUE(2)
GEEKS TRAINING = JUST PREVIOUS DAY trained RUNNING(0), FIGHTING(1), LEARNING(2)

So in INCLUSION / EXCLUSION DP
1) DEPENDENT ON WHAT ACTION WE TOOK ON JUST THE PREVIOUS LEVEL(level - 1),  (SO just need to track what we did on last level with the help of an TRACKER INTEGER)
2) ONLY FEW ACTIONS CAN BE PERFORMED AT ANY LEVEL, so the TRACKER INTEGER state is VERY LIMITED(2 states or 3 states at max, 2 or 3 possible values)

OBSERVATION INFERRED-
IN INCLUSION / EXCLUSION DP, generally a memo with key, MEMO(index/level, TRACKER INTEGER) would be sufficient to GET ALL TEST CASES PASSED.
The memo solution would ALWAYS be O(N) as there can be O(N) states in worst case, because level is in range[0, N - 1](as we process each element individually) and TRACKER INTGER has very few states (A CONSTANT NUMBER OF STATES => {2, 3}), IT'S DIMENSION would be a CONSTANT.

IN HOUSE ROBBER - memo(n, 2) = N X 2 (constant dimension of 2, because actions can be ROB/DON'T ROB)
IN PAINT HOUSE - memo(n, 3) = N X 3 (constant dimension of 3, because actions can be RGB)

TOTAL UNIQUE STATES =  MEMO(level, TRACKER INTEGER) => MEMO(N, 2 or 3) => MEMO(2N or 3N) => O(N)



JUMP DP - It depends on what LAST LEVEL/INDEX/ELEMENT was picked before the current level, and the last LEVEL/INDEX/ELEMENT picked is NOT NECESSARILY the JUST PREVIOUS INDEX OF current level(level - 1), it can be ANYTHING BEFORE current level [0, level - 1] unlike INCLUSION/EXCLUSION DP where it is ALWAYS about what happend on JUST THE PREVIOUS INDEX (level - 1)

We will maintain an INTEGER TRACKER lastElementIdx just like INC/EXC DP, but the DIFFERENCE here is lastElementIdx can have MANY/MULTIPLE STATES, ANYTHING IN RANGE[0, level - 1]. As level is dependent on N and ranges from [0, N - 1], lastElementIdx can have O(N) states as well.

So in JUMP DP
1)DEPENDS on WHICH LAST level/element was picked before CURRENT level/element.
(Tracker Integer lastElementIdx tracks which previous level/element was picked/actioned upon(any level before the current), unlike INC/EXC dp where it tracks WHAT action we took on the JUST PREVIOUS LEVEL(level just before current, i.e. (level - 1))
2) Here lastElementIdx ranges from [0, level - 1], i.e. not just the previous level (level - 1), ANY LEVEL BEFORE CURRENT LEVEL. As it can be anything before current index/level, it will require O(N) space. Dimension is not a CONSTANT.

********VERY IMPORTANT
OBSERVATION INFERRED-
IN JUMP DP problems, generally a memo key, MEMO(level, TRACKER INTGER) => MEMO(level, lastElementIdx) would NOT be SUFFICIENT to get ALL the TEST CASES PASSED.

PROBLEMS-
1) Constraints on N are tight (<= 10^6 / 10^5), which makes it IMPOSSIBLE TO declare 2D memo(level, lastElementIdx) table of size N^2.
2) If somehow memory is allocated to the memo table, with some looser constraints:
a) Time Complexity even though GENERALLY it is O(N^2), it would result in TLE. The major REASON behind that is LESS OVERLAPPING SUBPROBLEMS and hence more recursive calls. Most of the subproblems would be unique because of 2 keys which has many combinations memo(N, N), N^2 possible comibinations. So less overlap and more calls.
b) IF done via BLIND RECURSION(level + 1 to explore all levels), INVALID LEVELS will also be explored, causing recursive TREE to branch more, and hence more calls.

FIXES:
1) Constraints are tight: INSTEAD OF TRACKING lastElementIdx to validate which options are valid on levels, USE a LOOP(in cases of subsequence/order dependent/original array can't be modified/can't sort) or BINARY SEARCH(in cases of subsets/order independent/original array can be modified/sorted) on each level to SKIP the INVALID LEVELS, and ONLY CALL/MOVE to VALID LEVELS, WHERE ALL OPTIONS ARE VALID TO EXPLORE(especially the BEST OPTION that maximises/builds the best answer). As we only explore levels which has EVERY option as VALID(no need to worry/use a conditional on lastElementIdx to validate if this option will violate the property defined in the question) we explore only that SINGULAR BEST OPTION.
MOVING TO ONLY VALID LEVELS happen with the USE of LOOP OR BS, where instead of moving blindly to the next level and use conditional in next level to verify if level is valid or not, we PRE CHECK if the NEXT LEVEL we are moving to IS VALID OR NOT *RELATIVE* TO THE CURRENT LEVEL(IMPORTANT). If it is valid, then only MOVE to that level. SO USING LOOPS REMOVE THE OVERHEAD OF TRACKING lastElementIdx and it can be dropped from memo key. So Table is now 1d memo(level) => memo(10^6) which is allocatable.

2)
a) Time complexity reduces drastically, as now MORE SUBPROBLEMS WOULD OVERLAP, HENCE LOWERING THE CHANCES OF CACHE MISS.
MORE SUBPROBLEMS WOULD OVERLAP as previously memo(level, lastElementIdx) would IDENTIFY MORE UNIQUE STATES(N^2) different states possible so N^2 CACHE MISS. But not memo(level), which IDENTIFIES ONLY 'N' UNIQUE SUBPROBLEMS, so the sub problems that were being classifed into 2 different memo keys(level, lastElementIdx) because of different values at lastElementIdx, it would now be considered the same problems. And as lastElementIdx is O(N), so casually speaking, N different subproblems that were being put into different memo cells just because the value of lastElementIdx was unique for them, now dropping lastElementIdx from memo table, all of those 'N' different subproblems with UNIQUE VALUES OF lastElementIdx & the same value of level would now be classified into 1 big subproblem.

So previously,the set of these subproblems were different {R(8, 0), R{8, 1}, R{8, 2}, R{8, 3}, R{8, 4}, R{8, 5}, R{8, 6}, R{8, 7}} but as we dropped the 2nd key, all of these states are now reduced to {R(8), R(8), R(8), R(8), R(8), R(8), R(8), R(8)}, which you can see are all same.

AND..........

Dropping the 2nd key, reduces the total number of states {from N^2 to N} that needs calculation in the recursive function which decreases the time complexity by a factor of N. Previously we did the calculation for N^2 different problems in recursion. I think it would be mean the same (more overlapping subproblems <----> less calculation; cause <--> effect)


b) some states are almost always skipped while forming a path in the tree, so explored less states, less time taken.



*******IMPORTANT
Generally we explore ALL the VALID LEVELS RELATIVE TO CURRENT LEVEL VIA LOOP) (we move to ALL/EACH VALID LEVEL, and then BACKTRACK to form every possible combination with valid levels)(LIS, LONGEST DIVISIBLE SUBSET)

Sometimes, instead of exploring ALL the VALID LEVELS RELATIVE to CURRENT LEVEL VIA LOOP/BS (we ONLY move the *FIRST VALID* OR *JUST THE NEXT VALID* LEVEL AFTER OUR CURRENT LEVEL), basically out of all valid options, we GREEDILY choose the BEST of all VALIDS (Like in CSES PROJECTS, we choose the FIRST VALID/JUST THE NEXT VALID as  FIRST meeting that starts just after our current meeting ends/JUST THE NEXT meeting that starts AFTER our current meeting ends. It is the best thing to do here, because as soon as our current meeting ends in a path, we choose the first meeting/closest meeting that starts just after it(even if there are more meetings that starts after our current), because we MINIMISE the TIME being wasted in between the meetings, greedily forming the best answer.

************ VERY VERY IMPORTANT
RULE OF THUMB - IF THERE ARE MULTIPLE LEVELS THAT ARE VALID RELATIVE TO CURRENT LEVEL:
1) IF YOU CAN GREEDILY CHOOSE A SINGLE LEVEL, i.e. THE FIRST VALID/JUST THE NEXT VALID AFTER CURRENT, USE BINARY SEARCH
2) IF YOU CAN'T SINGLE LEVEL CHOOSE GREEDILY, i.e. YOU NEED TO EXPLORE ALL THE VALIDS AFTER CURRENT, USE LOOP
There can be many reason of not being able to choose a single greedy value, but I think it ALMOST ALWAYS depends on these 2:
a) IF the array is NOT SORTED or answer needed in SUBSEQUENCE (you have to check all the valids then)

eg for a)- IN QUESTIONs SIMILAR TO LIS (if the array were to be SORTED), because you need to build the longest sequence, assume all the valid levels to be the set K {j1, j2, j3, j4} and K to be current element. For the set to be valid for LIS, every (Ji > K) and (index(Ji) > index(K)). You can MOVE to a SINGLE VALID LEVEL GREEDILY, instead of EXPLORING ALL THE VALID LEVELS. Out of all valid levels, move to the SMALLEST VALID LEVEL, i.e. SMALLEST ELEMENT THAT IS GREATER THAN current element(here j1). Because moving to an element that is just greater than current element, doesn't violate the property of LIS and GIVES YOU THE BEST CHANCE TO FORM A LONGER SEQUENCE, as you CHOSE THE SMALLEST ELEMENT out of ALL ELEMENTS GREATER THAN CURRENT ELEMENT. Because the array is SORTED, order followed is K < j1 < j2 < j3 < j4. So all the other elements greater than CHOSEN ELEMENT (j1), will help build larger sequence as the options available after picking j1 are {j2, j3, j4}. If we would have picked {j2} after K to form the sequence, then the possible option reduces {j3, j4} which will reduce the max length by 1 as j1 can never be picked once j2 has been picked BEFORE in sequence
{...., K, j2, j1(X)} as this would violate the propery of longest increasing subsequence. j1 < j2 but index(j1) > index(j2).


b) If the ARRAY IS SORTED, BUT NOT ABLE TO THROW/DISREGARD THE HALF during BINARY SEARCH, because the mid value doesn't mean anything or monotonicity of the array is not applicable to decision making process (arr[mid] % arr[currentlevel] == 0), as MODULUS is NOT MONOTONIC.
Binary search is not safe here unless the PREDICATE(logic/condition = arr[mid] % arr[current LEVEL]) you’re searching on is monotonic, i.e., once it's false, it's always false beyond that point (or vice versa).

THIS IS WHAT I FOUND OUT(discussion with GPT) WHEN I DID THE LONGEST DIVISIBLE SUBSET QUESTION -
I think I know what NOT ENOUGH MONOTONIC means here. If we have already found an answer, we move to right in hopes that it become divisible enough(as %(mod) value might increase). But mod can also increase on the left half. imagine we are on 2 and we check range with number  from index + 1 {4, 5, 8, 9, 11}. The answer to this problem will be 3.(2, 4, 8). But if we take 2 then use BS to move to the next valid..it will be 8, as the mid is 8, we move to RIGHT according to your reasoning, and we will not find 4 as we move l = mid + 1. So the length will only come to be 2?


GPT -

v = {2, 4, 5, 8, 9, 11}


From index 0 (value 2), the valid next elements that satisfy v[next] % v[index] == 0 are:

4 → valid

8 → valid
(5, 9, 11 → invalid)

So the longest subset is: [2, 4, 8], which is length 3.

You're trying to find the first element ≥ index + 1 where v[mid] % v[index] == 0, assuming the rest will be useless or redundant. But that’s not always the best path. Binary search in this form will skip valid elements like 4 if it lands at 8 first and assumes it found the "first" valid.

But divisibility is not a monotonic predicate, meaning:

If v[i] % v[x] != 0, then we cannot rule out that v[i+1] % v[x] == 0.
Modulo doesn't increase or decrease predictably in sorted arrays.

THIS MEANS WE CAN'T CHOOSE A SINGLE GREEDY VALUE HERE.*******************

CORRECT STRATEGY:
Rather than using binary search to find the next valid, you should:

Loop through ALL i > index (after sorting, sorting can be done as question demands a subset).

For every i, check if v[i] % v[index] == 0

Recurse from EACH such vVALIDlid index.

Memoize based on index (not level, not lastIdx).
lastElementIdx is not required now,, because we only move to the valid levels where including the element doesn't violate the property of subset, because we came to this level, ONLY AFTER WE PRE CHECKED THAT THIS LEVEL WON'T VIOLATE ANYTHING with the help of loop.



Question - If the mid value doesn't mean anything or doesn't help in binary search because the predicate isn't monotonic, can we loop and take the first smallest valid value instead (choosing a single element greedily) in this particular question? AS we can take the smallest number divisible by the current element, because it is smallest number divisible by current element, would it not maximise the chances of building a longer chain as it is smallest number in the sequence, and we would have larger numbers after that and because the property is {a1|a2|a3...} so if a2 is divisible by a1 and a3 is divisible by a2, then a1 can also divide a3, because it is a common factor of a2 and a3. So choosing the closest element won't give the best chance of building better sequence.? What could be contradictory with an example or what could be general idea/proof/axiom/postulate that can answer the question.


SUMMARY-
IN INC/EXC, When on STATE(level), in Recursion we track WHICH ACTION on STATE(level - 1)?
IN JUMP DP, When on STATE(level), in Recursion we track WHICH LEVEL before STATE(level) was LAST ACTIONED UPON.
WHICH STATE(level - i), where 0 < i <= level before STATE(level) ACTIONED UPON LAST? Generally there is a SINGLE BEST OPTION out of ALL the OPTIONS. WE ONLY MOVE TO VALID LEVELS, VALID LEVELS ARE THOSE LEVELS WHERE THE SINGULAR BEST OPTION IS ALWAYS VALID TO BE EXPLORED,  so for EACH VALID LEVEL we move to, WE ONLY EXPLORE THAT SINGULAR BEST OPTION. THE SINGULAR BEST OPTION is what MAXIMISES the answer(VALUE of subsequence/subset) by adding profit or BUILDS THE LONGEST  answer(SIZE of subsequence/subset) by including/adding element to the SUBSEQUENCE/SUBSET.

Just like what we do in:
1)CSES question PROJECTS(ONLY EXPLORE VALID LEVELS, WHERE THE SINGULAR BEST OPTION TO ATTEND THE MEETING,  IS ALWAYS VALID,attend that MEET & TAKE PROFIT which MAXIMISES the VALUE of answer).
2)LIS(ONLY EXPLORE VALID LEVELS, WHERE THE SINGLUAR BEST OPTION TO INCLUDE THE ELEMENT, IS ALWAYS VALID, include that valid level element & increment subsequence size by 1, which MAXIMISES the SIZE of answer).
3) Question such as LONGEST DIVISIBLE SUBSET(ONLY EXPLORE VALID LEVELS, WHERE THE SINGLULAR BEST OPTION TO INCLUDE THE ELEMENT, IS ALWAYS VALID, include the valid element & increment subsequence size by, which MAXMISES the SIZE of answer)

| Type                        | Problem Style                 | Key State                 | Tracker Dim        | Space         | Loop/BS Use |
| --------------------------- | ----------------------------- | ------------------------- | ------------------ | ------------- | ----------- |
| Inclusion/Exclusion         | Robber, Paint House           | `memo(level, tracker)`    | Small (2–3)        | O(N)          | Not needed  |
| Jump DP (All Valid)         | LIS, Longest Div Subset       | `memo(level)` (with loop) | Tracker eliminated | O(N)          | Use loop    |
| Jump DP (Next Valid Greedy) | CSES Projects                 | `memo(level)` (with BS)   | Tracker eliminated | O(N)          | Use BS      |
| Naive Jump DP               | Original memo(level, lastIdx) | Large O(N²)               | O(N²)              | TLE/MLE prone |             |

*/

    bool isPossibleToReachMapVersion(int level, int lastJump, vector<int> &stones, unordered_map<int, int> &stoneMappings, vector<vector<int> > &memo){
        // cout << path << '\n';
        if(level == stones.size() - 1){
            return true;
        }
        if(memo[level][lastJump] != -1){
            return memo[level][lastJump];
        }
        //levels = stones
        //options = k - 1, k , k + 1
        //invalid k = 0
        //jump only if the stone exist
        bool possible = false;
        for(int i = -1; i < 2; i++){
            int jump = lastJump + (int) i;
            if(jump > 0){
                //The next stone where we jump from current stone exist in map or not
                int nextStone = stones[level] + jump;
                if(stoneMappings.count(nextStone) > 0){
                    possible |= isPossibleToReachMapVersion(stoneMappings[nextStone], jump, stones, stoneMappings, memo);
                }
            }
        }
        return memo[level][lastJump] = possible;
    }

    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int> > memo(n, vector<int>(n, -1));
        //APPROACH 1 + minSteps
        // long long steps = getMinSteps(0, 0, stones, memo);
        // // cout << steps << '\n';
        // return steps > 0 && steps != INT_MAX? true : false;


        //APPROACH 2 only true/false
        // return isPossibleToReach(0, 0, stones, memo);


        //Approach 2(no bs, do binary search)
        //map(stone, stoneIdx)
        unordered_map<int, int> stoneMappings;
        for(int i = 0; i < stones.size(); i++){
            stoneMappings[stones[i]] = i;
        }
        return isPossibleToReachMapVersion(0, 0, stones, stoneMappings, memo);
    }
};