The Trials and Tribulations of Dynamic Programming

Holy moly neetcode has been in my ear everyday... EVERYDAY!!!

So What's the 'ish Bro

What is the issue indeed!
So I've been on the leetcode grind recently trying to improve proscpects and become a better problem solver in general. To do this I've been following trhe roadmap created by every programmer's best friend:
NEETCODE <-- if you haven't already go make an account on his site
And I've the core of the roadmap tree without having to look up solutions, this is topics up to Heaps and Backtracking. However, although I can puzzle out solutions, I don't have a deeper understanding about the efficiencies of some of those topics, namely recursion, of which I will get into further down this blog.
The step after backtracking is graphs and 1-D Dynamic Programming. Graph algorithms are challenging, but the data structures are usually straightforward to visualize. Dynamic Programming (DP) on the other-hand is a devil. I've only done most of them via some terrible memoization techniques, of which I had a piss poor concept of until now. So today's blog is a journey of recursion, memoization, redeption, and the future!!!

So what to do about the ish???

Before I say anything and ramble and confuse more than assist, this video is what level upped my DP pls watch:
This guy knows his DP and how to show it (winky face)
To prepose my explination of my process I will be using a classic problem called "coin change" to demonstrate what the H is goin on.
The problem is to find the least amount of coins it takes to create change for a given number of cents. You are given a list of different coin denoominations of which you can make change with. Ex:
Make 11 cents given 1 cent, 2 cent, and 5 cent coins.
You can use two 5 cent coins and one 1 cent coint, or fice 2 cent coins and one 1 cent, etc and so on...
The solution comes down to checking every possible combination of coins. Pee Yew!

Its really just a problem with recursion

Like the title of this section, it really is a probalem of recursion. Since I got the hand of backtracking, I got into this really bad habit of not using return values in recursion and instead just passing pointers of shared variables and making sure to manually remove and add-back in elements to
To translate recursion and backtracking into DP you need to use the return values so your functions are ambiguous to input! I was not doing this! Look at this hot mess that was my first solution to coin change:

import java.util.*;
class Solution {
    public int coinChange(int[] coins, int amount) {
        //backtrack starting from the greatest coin
        //keep track of totals already reached, because we already checked those
        HashMap<Integer,Integer> totals = new HashMap<>();
        if(amount==0)return 0;
        Arrays.sort(coins);
        int[] sumCount = {0,0};
        int[] pog = {-1};
        find(sumCount,coins,amount,pog,totals);
        return pog[0];
    }
    static void find(int[] sumCount, int[] coins,int amount, int[] pog,HashMap<Integer,Integer> totals){
        for(int i = coins.length-1; i >= 0;i--){
            //System.out.println(coins[i]+",");
            sumCount[0] += coins[i];
            sumCount[1]++;
            if((totals.containsKey(sumCount[0]) && totals.get(sumCount[0])<=sumCount[1])||coins[i]>10000){
                sumCount[0] -= coins[i];
                sumCount[1]--;
                continue;
            }else{
                totals.compute(sumCount[0],(k,v) -> v=sumCount[1]);
            }
            if(sumCount[0]==amount && (pog[0]==-1 || sumCount[1] < pog[0])){
                //System.out.println("hit!");
                pog[0] = sumCount[1];
            }else if(sumCount[0] < amount){
                //System.out.println("recurse on:"+coins[i]);
                find(sumCount,coins,amount,pog,totals);
            }
            sumCount[0] -= coins[i];
            sumCount[1]--;
        }
    }
}

The key I found is when I landed on a backtracking/recursive solution, look for a common subproblem. That being said it is not usually very easy to puzzle out. However once you use the following memo formula on a few easier problems, harder 1-D DP gets easier in general, I have slowly increased my own solves of memoization problems.

Memoization is so cute

Memoization is literally creating a "memo" or ledger or dict or A GOTDANG HASHMAP IN JAVA to quite literally memorize answers to those "subproblems".
To construct this though we need subproblems to base the answer keys off of. THIS IS WHY TREES IS A PRECEDING TOPIC IN THE ROADMAP. With backtracking and recursion and 1-D DP always visualize you solution before jumping into code. When you make recursive calls you will see it creates a tree data structure. Of which the nodes can be crafted into values of those subproblem solutions. Looky here:
That is a part of the tree of recursion created from my following solution of the coin change example from earlier!

class Solution {
    public int coinChange(int[] coins, int amount) {
        HashMap<Integer,Integer> memo = new HashMap<>();
        return coinChange(coins,amount,memo);
    }

    public int coinChange(int[] coins, int amount, HashMap<Integer,Integer> memo) {
        if(amount==0)return 0;
        if(memo.containsKey(amount))return memo.get(amount);
        for(int c : coins)if(c==amount)return 1;
        int lowest = Integer.MAX_VALUE;
        for(int c : coins)lowest = Math.min(lowest,c);
        if(amount<lowest)return -1;
        int holder = 0, change = Integer.MAX_VALUE;
        for(int c : coins){
            holder = 1+coinChange(coins,amount-c,memo);   
            if(holder == 0)continue;
            if(holder>0)change = Math.min(change,holder);
        }
        memo.put(amount,change);
        return change==Integer.MAX_VALUE?-1:change;
    }
}

Notice the difference between this code and the previous mess. Both loop over all coins at each step to check all possible permustations, but the former relies on a shared answer variable called "pog" while the ladder derives answers from lower rungs in the tree. Both skip doing extra work based on previous ansers, but the former memo redoes some work if there is a potentially better soltion to the subproblem (it is unsure) whereas the ladder finds the most efficient route for each value the first recurse down.
The video realy really explains it a ton better, and I will be looking into 2-D DP and tabulation soon (which the video also explains).

Thank you bye bye have a nice wekend (kissy face smile) ( ˘ ³˘)♥

Productive week for me, hopefully to you and yours. Or relax idk do something that improves you well being!
~ Vince