Dynamic Programming algorithms

AAA_DP.txt

Dynamic Programming algorithms

DPUtils.java

package com.blogspot.groglogs.dp;

import com.blogspot.groglogs.structures.Pair;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class DPUtils {

    //only used when testing caching vs non caching for total number of calls
    private static int TOT_CALLS;

    //helper for maxRodCutProfit
    private static int maxRodCutProfitRec(int[] lengthProfits, int rodSize){
        /*
        Use recursive approach, for rod of length N we explore all possible cuts.
        Each time we pick the best choice between cutting at length i or not.
        If we do cut, our best is profit for cut length + max profit for a rod of length size - cut.
        We compare all these possibilities to find the max.
        We stop when rod length is 0 as we can't cut anymore.
         */
        if(rodSize == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        //go all the way up to rodSize, which means we don't cut it
        for(int curLength = 1; curLength <= rodSize; curLength++){
            //lenghtProfits curLength - 1 since it's a 0 based array
            max = Math.max(max, lengthProfits[curLength - 1] + maxRodCutProfitRec(lengthProfits, rodSize - curLength));
        }
        return max;
    }

    /**
     * Given a rod of a certain length and a table with the profits from selling rods of a particular length, find the
     * best way to cut the rod to maximize profit. No cut is also allowed.
     * No optimizations approach.
     * @param lengthProfits an array tracking the profit from selling a rod of length i + 1.
     * @param rodSize the length of the rod to cut.
     * @return the maximum profit that can be made by cutting the rod.
     */
    public static int maxRodCutProfit(int[] lengthProfits, int rodSize){
        if(lengthProfits == null || rodSize <= 0 || lengthProfits.length < rodSize){
            return -1;
        }

        return maxRodCutProfitRec(lengthProfits, rodSize);
    }

    //helper for maxRodCutProfitDP
    private static int maxRodCutProfitRecDP(int[] lengthProfits, int rodSize, int[] cache, int[] lengths){
        /*
        Same as maxRodCutProfitRec, however we cache already computed values.
        Cache is of length rodSize + 1 where 0 indicates a rod of length 0.
        Cache is initialized to -1.
         */
        //if cached value exists, return that
        if(cache[rodSize] > -1){
            return cache[rodSize];
        }
        int max = Integer.MIN_VALUE;
        //rod of length 0 has 0 profit
        if(rodSize == 0){
            max = 0;
        }
        else {
            //do the calculation but cache the result as well
            //go all the way up to rodSize, which means we don't cut it
            for (int curLength = 1; curLength <= rodSize; curLength++) {
                //lenghtProfits curLength - 1 since it's a 0 based array
                //can't use max only as we need to know what did we pick to update the best cut length for this max profit
                //max = Math.max(max, lengthProfits[curLength - 1] + maxRodCutProfitRecDP(lengthProfits, rodSize - curLength, cache, lengths));
                int currCutBest = lengthProfits[curLength - 1] + maxRodCutProfitRecDP(lengthProfits, rodSize - curLength, cache, lengths);
                if(currCutBest > max){
                    max = currCutBest;
                    lengths[rodSize] = curLength;
                }
            }
        }
        cache[rodSize] = max;
        return max;
    }

    /**
     * Given a rod of a certain length and a table with the profits from selling rods of a particular length, find the
     * best way to cut the rod to maximize profit. No cut is also allowed.
     * Uses top down DP approach.
     * @param lengthProfits an array tracking the profit from selling a rod of length i + 1.
     * @param rodSize the length of the rod to cut.
     * @return the maximum profit that can be made by cutting the rod.
     */
    public static Pair<Integer, List<Integer>> maxRodCutProfitDP(int[] lengthProfits, int rodSize){
        Pair<Integer, List<Integer>> result = new Pair<>(-1, new ArrayList<>());
        if(lengthProfits == null || rodSize <= 0 || lengthProfits.length < rodSize){
            return result;
        }

        //cache of size rod length + 1 so in position 0 we have profit for rod of length 0
        //since in profits array in position 0 (0 based) we have profit for rod of length 1
        int[] cache = new int[rodSize + 1];
        for(int i = 0; i < cache.length; i++){
            cache[i] = -1;
        }
        //here we also track the best cut size for this rod length, in order to reconstruct the solution later
        int[] lengths = new int[rodSize + 1];

        int max =  maxRodCutProfitRecDP(lengthProfits, rodSize, cache, lengths);

        //best profit is in our cache
        result.setFirst(max);
        //we backtrack to find all optimal cuts for that profit, starting for optimal cut for best
        List<Integer> cuts = result.getSecond();
        cuts.add(lengths[rodSize]);
        //walk down (if any) all subcuts we did to reach this profit, and add those lengths to the result
        int i = rodSize - lengths[rodSize];
        while(i > 0){
            cuts.add(lengths[i]);
            i -= lengths[i];
        }
        result.setSecond(cuts);
        return result;
    }

    /**
     * Given a rod of a certain length and a table with the profits from selling rods of a particular length, find the
     * best way to cut the rod to maximize profit. No cut is also allowed.
     * Uses bottom up DP approach.
     * @param lengthProfits an array tracking the profit from selling a rod of length i + 1.
     * @param rodSize the length of the rod to cut.
     * @return the maximum profit that can be made by cutting the rod.
     */
    public static Pair<Integer, List<Integer>> maxRodCutProfitDPBottomUp(int[] lengthProfits, int rodSize){
        Pair<Integer, List<Integer>> result = new Pair<>(-1, new ArrayList<>());
        if(lengthProfits == null || rodSize <= 0 || lengthProfits.length < rodSize){
            return result;
        }

        /*
        Similar to maxRodCutProfitRecDP but without recursion.
        Instead of cutting from rodSize down to 0, we expand from 0 to rodSize
        cache initialized to 0 this time (really we only need cache[0] = 0) as we expand from there
         */
        int[] cache = new int[rodSize + 1];
        //here we also track the best cut size for this rod length, in order to reconstruct the solution later
        int[] lengths = new int[rodSize + 1];

        //go all the way up to rodSize, which means we don't cut it
        for(int size = 1; size <= rodSize; size++){
            int max = Integer.MIN_VALUE;
            //all the possible cuts from 1 to current rodSize
            for(int cutLength = 1; cutLength <= size; cutLength++){
                //take current cut (cutLength - 1 as it's 0 based) plus best cut for remaining rod length after this cut
                //since all smaller lengths we have already calculated before, it will be in the cache
                //can't use max only as we need to know what did we pick to update the best cut length for this max profit
                //max = Math.max(max, lengthProfits[cutLength - 1] + cache[size - j]);
                int currCutBest = lengthProfits[cutLength - 1] + cache[size - cutLength];
                if(currCutBest > max){
                    max = currCutBest;
                    lengths[size] = cutLength;
                }
            }
            cache[size] = max;
        }

        //best profit is in our cache
        result.setFirst(cache[rodSize]);
        //we backtrack to find all optimal cuts for that profit, starting for optimal cut for best
        List<Integer> cuts = result.getSecond();
        cuts.add(lengths[rodSize]);
        //walk down (if any) all subcuts we did to reach this profit, and add those lengths to the result
        int i = rodSize - lengths[rodSize];
        while(i > 0){
            cuts.add(lengths[i]);
            i -= lengths[i];
        }
        result.setSecond(cuts);
        return result;
    }

    //helper for minCostToPaintHouses
    private static int minCostToPaintHousesRec(int[][] costToPaintHouseWithColor, int numHouses, int numColors, int house, int excludeColor, Map<Pair<Integer, Integer>, Integer> cache){
        int cost = cache.getOrDefault(new Pair(house, excludeColor), -1);
        if(cost != -1){
            return cost;
        }
        //reached end of houses, no more paint to use, cost is 0
        if(house == numHouses){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        //try all possible colors EXCEPT the excluded one
        for(int color = 0; color < numColors; color++){
            if(color == excludeColor){
                continue;
            }
            //total cost is painting the house using this color + cost of painting the next EXCLUDING this color
            min = Math.min(min, costToPaintHouseWithColor[house][color] + minCostToPaintHousesRec(costToPaintHouseWithColor, numHouses, numColors, house + 1, color, cache));
            cache.put(new Pair<>(house, excludeColor), min);
        }

        return min;
    }

    /**
     * Given a matrix with rows = houses and columns = cost to paint house of that color, find the minimum cost of painting
     * all houses such that no two adjacent houses have the same color.
     * @param costToPaintHouseWithColor a matrix with rows = houses and columns = cost to paint house of that color.
     * @return the minimum cost of painting all houses such that no two adjacent houses have the same color.
     */
    public static int minCostToPaintHouses(int[][] costToPaintHouseWithColor){
        //need at least two colors for this to make sense
        if(costToPaintHouseWithColor == null || costToPaintHouseWithColor.length == 0 || costToPaintHouseWithColor[0].length < 2){
            return -1;
        }
        int numHouses = costToPaintHouseWithColor.length;
        int numColors = costToPaintHouseWithColor[0].length;

        //key = (house, excluded color), value = min total cost of painting that house excluding that color
        Map<Pair<Integer, Integer>, Integer> cache = new HashMap<>();

        return minCostToPaintHousesRec(costToPaintHouseWithColor, numHouses, numColors, 0, -1, cache);
    }

    //helper for longestCommonSubsequence
    private static int longestCommonSubsequenceRec(String a, String b, int a_idx, int b_idx, int[][] cache){
        //one of the two strings is finished
        if(a_idx >= a.length() || b_idx >= b.length()){
            return 0;
        }

        //we have a cached value
        if(cache[a_idx][b_idx] != -1){
            return cache[a_idx][b_idx];
        }

        /*
        otherwise max is:
        - if curr char for A and B are equal, we are expanding on a subsequence so 1 + best of subsequence AFTER these chars
        - else max of (subsequence starting from current index in A and NEXT index in B)
        and (subsequence starting from NEXT index in A and current index in B)
         */
        int max;
        if(a.charAt(a_idx) == b.charAt(b_idx)){
            max = 1 + longestCommonSubsequenceRec(a, b, a_idx + 1, b_idx + 1, cache);
        }
        else{
            max = Math.max(longestCommonSubsequenceRec(a, b, a_idx, b_idx + 1, cache),
                    longestCommonSubsequenceRec(a, b, a_idx + 1, b_idx, cache));
        }

        cache[a_idx][b_idx] = max;

        return max;
    }

    /**
     * Given two strings, find the longest common subsequence.
     * @param a the first string.
     * @param b the second string.
     * @return the longest common subsequence.
     */
    public static String longestCommonSubsequence(String a, String b){
        if(a == null || b == null || a.length() == 0 || b.length() == 0){
            return "";
        }

        /*
        cache is rows = subsequence of A starting at index i
        columns = subsequence of B starting at index j
         */
        int[][] cache = new int[a.length()][b.length()];
        for(int i = 0; i < a.length(); i++){
            for(int j = 0; j < b.length(); j++){
                cache[i][j] = -1;
            }
        }

        int max = longestCommonSubsequenceRec(a, b, 0, 0, cache);

        //don't run a search if length was 0
        if(max == 0){
            return "";
        }

        StringBuilder sb = new StringBuilder();
        int a_idx = 0;
        int b_idx = 0;

        //if we look at the cache we can reconstruct the solution from the first matching character
        while(a_idx <= a.length() - 1 && b_idx <= b.length() - 1){
            //in this case we would have moved diagonally to next character on both strings
            if(a.charAt(a_idx) == b.charAt(b_idx)){
                sb.append(a.charAt(a_idx));
                a_idx++;
                b_idx++;
            }
            else {
                //in this case we would have moved forward from either string
                //if we still have characters in both, find which one we moved from
                 if (a_idx < a.length() - 1 && b_idx < b.length() - 1){
                     //in this case we would have used the next character from A
                     if(cache[a_idx + 1][b_idx] >= cache[a_idx][b_idx + 1]){
                         a_idx++;
                     }
                     //in this case we would have used the next character from B
                     else{
                         b_idx++;
                     }
                 }
                 //otherwise we have reached the end of a string, stay there and move forward from the other
                 //if both are at the end and we did not find a match previously, move either forward to break out of the loop
                 else if(a_idx == a.length() - 1){
                     b_idx++;
                 }
                 else {
                     a_idx++;
                 }
            }
        }

        return sb.toString();
    }

    /**
     * Given two strings, find the longest common subsequence.
     * @param a the first string.
     * @param b the second string.
     * @return the longest common subsequence.
     */
    public static String longestCommonSubsequenceString(String a, String b){
        if(a == null || b == null || a.length() == 0 || b.length() == 0){
            return "";
        }

        /*
        //optional - this is used to be able to backtrack and find the actual subsequence once we have the solution
        final int BACK_DIAG = -2;
        final int BACK_UP = -1;
        final int BACK_LEFT = 1;
         */

        /*
        Using bottom up approach, we apply logic similar to longestCommonSubsequenceRec but include the case where strings
        have length 0 (our starting problem). In those cases, the best subsequence has length 0
        Then for each combination of characters from A and B, we decide what to pick in a similar way:
        - if curr char for A and B are equal, we are expanding on a subsequence so 1 + best of subsequence BEFORE these chars
        - else max of (subsequence starting from current index in A and PREV index in B)
        and (subsequence starting from PREV index in A and current index in B)

        since we are doing bottom up, we have already calculated the best solution for previous subproblems

        optional: our matrix has the full words as rows and columns, so we can store which directions did we take while
        getting the best solution in a separate matrix.
        The matching characters will be on diagonal movements (only time where we move diagonally in the cache is when chars
        in both strings match) and the best choices for non matches will either be moving to a PREVIOUS char in either string,
        thus the "up" and "left" simply mean "PREVIOUS char in A" (since string A was placed as rows) and "PREVIOUS char in B"
        (since string B was placed as columns).
         */
        int[][] cache = new int[a.length() + 1][b.length() + 1];
        //int[][] backtrack = new int[a.length() + 1][b.length() + 1];

        for(int a_idx = 1; a_idx <= a.length(); a_idx++){
            for(int b_idx = 1; b_idx <= b.length(); b_idx++){
                //same char means we are expanding on a best subsequence, previous best for both strings is diagonally BEFORE current indexes
                if(a.charAt(a_idx - 1) == b.charAt(b_idx - 1)){
                    cache[a_idx][b_idx] = 1 + cache[a_idx - 1][b_idx - 1];
                    //backtrack[a_idx][b_idx] = BACK_DIAG;
                }
                else{
                    //find which previous best we are choosing and set it as current best for these indexes
                    cache[a_idx][b_idx] = Math.max(cache[a_idx - 1][b_idx], cache[a_idx][b_idx - 1]);
                    /*
                    //optional - track also from which string did we get the best value so we can recreate the solution later
                    int up = cache[a_idx - 1][b_idx];
                    int left = cache[a_idx][b_idx - 1];
                    if(up > left){
                        backtrack[a_idx][b_idx] = BACK_UP;
                    }
                    else{
                        backtrack[a_idx][b_idx] = BACK_LEFT;
                    }
                    cache[a_idx][b_idx] = Math.max(left, up);
                    */
                }
            }
        }

        //don't run a search if length was 0
        if(cache[a.length()][b.length()] == 0){
            return "";
        }

        //backtrack from bottom right all the way to the longest subsequence (we create in reverse order)
        StringBuilder sb = new StringBuilder();
        int a_idx = a.length();
        int b_idx = b.length();

        /*
        //optional - use backtrack matrix
        while(a_idx >= 0 && b_idx >= 0){
            switch (backtrack[a_idx][b_idx]){
                //if we had moved left, we used the PREVIOUS char from string B
                case BACK_LEFT:
                    b_idx--;
                    break;
                //if we had moved up, we used the PREVIOUS char from string A
                case BACK_UP:
                    a_idx--;
                    break;
                //otherwise chars in B and A were a match, add to result and move diagonally BACK
                case BACK_DIAG:
                    sb.append(a.charAt(a_idx - 1));
                    a_idx--;
                    b_idx--;
                    break;
                //stop as soon as we have no more indications for backtracking
                default:
                    a_idx = -1;
            }
        }*/

        //if we look at the cache and backtrack matrix we can see the pattern that allows us
        //to reconstruct the solution using only the cache
        while(a_idx > 0 && b_idx > 0){
            //in this case we would have moved diagonally
            if(a.charAt(a_idx - 1) == b.charAt(b_idx - 1)){
                sb.append(a.charAt(a_idx - 1));
                a_idx--;
                b_idx--;
            }
            //in this case we would have used the previous character from A
            else if(cache[a_idx - 1][b_idx] >= cache[a_idx][b_idx - 1]){
                a_idx--;
            }
            //in this case we would have used the previous character from B
            else{
                b_idx--;
            }
        }

        //result subsequence is in reverse order, reverse again and finally return it
        return sb.reverse().toString();
    }

    /**
     * Given two strings, return the dp matrix for the longest common subsequence.
     * @param a the first string.
     * @param b the second string.
     * @return the dp matrix for the longest common subsequence.
     */
    public static int[][] longestCommonSubsequenceCache(String a, String b){
        if(a == null || b == null || a.length() == 0 || b.length() == 0){
            return new int[][]{};
        }

        int[][] cache = new int[a.length() + 1][b.length() + 1];

        for(int a_idx = 1; a_idx <= a.length(); a_idx++){
            for(int b_idx = 1; b_idx <= b.length(); b_idx++){
                //same char means we are expanding on a best subsequence, previous best for both strings is diagonally BEFORE current indexes
                if(a.charAt(a_idx - 1) == b.charAt(b_idx - 1)){
                    cache[a_idx][b_idx] = 1 + cache[a_idx - 1][b_idx - 1];
                }
                else{
                    //find which previous best we are choosing and set it as current best for these indexes
                    cache[a_idx][b_idx] = Math.max(cache[a_idx - 1][b_idx], cache[a_idx][b_idx - 1]);
                }
            }
        }

        return cache;
    }

    /**
     * Given a string, find the longest palindromic subsequence it contains.
     * @param s the string.
     * @return the longest palindromic subsequence it contains.
     */
    public static String longestPalindromicSubsequence(String s){
        if(s == null || s.length() == 0){
            return "";
        }

        /*
        We reverse the string, then check for the longest common subsequence. Assuming the string does contain a palindrome
        the reversal of the string will have that same palindrome appear, possibly in a different place.
        However, both the original and reversed string will share those common characters as part of some subsequence.
         */
        StringBuilder sb = new StringBuilder(s);

        return longestCommonSubsequence(s, sb.reverse().toString());
    }

    /**
     * Given an integer n, find how many possible BSTs can be created containing N nodes.
     * @param n the number of BST nodes.
     * @return the number of valid BSTs that can be created with those N nodes.
     */
    public static int numOfBSTs(int n){
        if(n <= 1){
            return 1;
        }
        int[] cache = new int[n + 1];
        cache[0] = 1;
        return numOfBSTs(n, cache);
    }

    /*
    A BST with 0 and 1 nodes can be constructed only in one way.
    For a given BST root and N nodes, we have the following options:
    - all nodes are on the left
    - all nodes are on the right
    - nodes smaller than root are on the left, nodes bigger than root are on the right

    which we can condense together in the last option considering two ranges: 1..root-1, root+1..N
    For a single root and N nodes therefore, the combinations of left and right subtrees generated this way is left*right
    we do this calculation for each possible root value in 1..N
    This is also the same number we can calculate for generic binary trees if we consider number of nodes rather than values.
     */
    private static int numOfBSTs(int n, int[] cache){
        if(cache[n] > 0){
            return cache[n];
        }
        int res = 0;
        for(int i = 1; i <= n; i++){
            res += numOfBSTs(i - 1) * numOfBSTs(n - i);
        }
        cache[n] = res;
        return res;
    }

    /**
     * Given an integer n, find how many possible BSTs can be created containing N nodes.
     * Bottom up approach. (Catalan number)
     * @param n the number of BST nodes.
     * @return the number of valid BSTs that can be created with those N nodes.
     */
    public static int numOfBSTsBottomUp(int n){
        int[] cache = new int[n + 1];
        cache[0] = 1;

        /*
        Same approach as before, but we must explicitly handle the ranges 1..root-1, root+1..N
        For each N therefore we calculate all possibilities from 0 to N - 1 to cover all N - 0, ..., N - (N - 1) cases
         */
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < i; j++){
                cache[i] += cache[j] * cache[i - j - 1];
            }
        }

        return cache[n];
    }

    /**
     * A wiggle subsequence is a sequence of alternating strictly increasing or decreasing numbers. Given a sequence of integers
     * find the longest wiggle subsequence.
     * @param nums the input numbers.
     * @return the longest wiggle subsequence.
     */
    public static int longestWiggleSubsequence(int... nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        if(nums.length == 1){
            return 1;
        }

        /*
        If we start with a recursive top down approach, we find ourselves calling a function:
        longestWiggleSubsequence(nums, currentElement, nextElement, direction)

        as can start the sequence going either up or down and picking or not the first element. We can represent these
        combinations with a cache [current][next][direction]

        Initially we would have:
        first,next,up = 1 //picked first element and going up to the next
        first,next,down = 1 //picked first element and going down to the next
        none,next,up = 0  //did not pick first element and going up to the next
        none,next,down = 0 //did not pick first element and going down to the next

        However, we can also split this cache up in two separate caches

        up = [current][next]
        down = [current][next]

        where each pair of current,next elements indicate a position in the array and tracks the longest wiggle subsequence
        until then.

        We notice that it's impossible to increase both subsequences at the same time as our choices for each pair are:
        - curr < next: we can expand the down sequence only if the previous chosen element was > curr
        - curr > next: we can expand the up sequence only if the previous chosen element was < curr
        - curr == next: we can't improve any sequence

        We could track the previous chosen element to implement this logic, but we again notice that the improvements
        only alternate between the two possible sequences:
        - curr < next: we are improving from the best prev > curr (down) sequence
        - curr > next: we are improving from the best prev < curr (up) sequence
        as otherwise we would be improving on an invalid always increasing or decreasing sequence

        We also notice we are looking at each pair current,next element once per sequence, so we don't need to track
        all combinations of elements, but only the best length for either sequence until a certain pair of elements. Our cache
        can become:

        up = [best sequence so far going up at this element]
        down = [best sequence so far going down at this element]

        We finally notice as well that we need to look at each pair of elements once and more importantly, the best decision for either
        up or down until that point will be the best decision overall as the sequence is either increasing or decreasing
        but we do not require more knowledge than the last chosen elements (and the best until there).

        We can therefore get rid of the arrays and use a simple variable.

        This is similar to the problem where we are asked to find the longest increasing subsequence of elements in an array
        with the twist that we are interleaving two increasing and decreasing subsequences instead.
         */

        //no matter if we pick the first element or not, if we have more than one element, our initial longest is 1
        //either we pick the first or will pick the second (and might continue or not from there)
        int up = 1;
        int down = 1;

        //for each new element see if we can improve on either sequence
        for(int i = 1; i < nums.length; i++){
            //curr > prev, we can only expand an up sequence from a down sequence
            //specifically we can only improve from the BEST down sequence until this point
            if(nums[i] > nums[i - 1]){
                up = down + 1;
            }
            //curr < prev, we can only expand a down sequence from an up sequence
            //specifically we can only improve from the BEST up sequence until this point
            if(nums[i] < nums[i - 1]){
                down = up + 1;
            }
        }

        //the best is the best of the two sequences
        return Math.max(up, down);
    }

    //helper for reconstructSentence
    private static StringBuilder canBreak(String s, int index, Set<String> words, Set<Integer> cache){

        StringBuilder sb = new StringBuilder();

        //empty string is always a valid break, we add a whitespace char to signal that
        if(index == s.length()){
            return sb.append(' ');
        }

        //if we already explored breaking off from this index, we know there is no solution, return empty StringBuilder
        if(cache.contains(index)){
            sb.setLength(0);
            return sb;
        }

        //for each char starting at this index, explore whether we can find a solution breaking off here
        //we only break off if the substring from start index to current index is a dictionary word
        for(int i = index; i < s.length(); i++){
            //expand on current suffix
            sb.append(s.charAt(i));
            //if current suffix is a dictionary word, check if breaking off here would give a valid sentence
            if(words.contains(sb.toString())){
                //explore the rest of the string after breaking off from here
                StringBuilder res = canBreak(s, i + 1, words, cache);
                //if this StringBuilder contains some words, we could successfully break off the next portion of text
                if(res.length() > 0){
                    //if length is exactly one, it is the whitespace we added since we explored an empty string
                    //so we do NOT add a whitespace between us and the next word as there is no next word
                    if(res.length() > 1){
                        sb.append(' ');
                    }
                    //append the rest of text to us to form the full sentence
                    return sb.append(res);
                }
            }
        }

        //if we get here, from the start index we couldn't find a solution, cache this information
        cache.add(index);

        //and return an empty StringBuilder to notify that
        sb.setLength(0);
        return sb;
    }

    /**
     * Given a text and a dictionary of words, return a possible sentence reconstruction by breaking the text in
     * multiple words.
     * @param words the dictionary words.
     * @param text the text to break.
     * @return a possible reconstruction of a sentence by breaking the text in multiple space separated words.
     */
    public static String reconstructSentence(Set<String> words, String text){
        if(words == null || text == null || words.isEmpty() || text.isEmpty()){
            return "";
        }

        /*
        We use DP and for each character in the string, we explore the possibilities of breaking off a word there
        or continuing with a longer word and breaking later.
        We cache whether we failed to find a valid sentence when breaking off at a specific index.
        We will find the sentence that uses the shortest words with this approach.
        We use a StringBuilder to track the sentence reconstructed so far, in the end we will either have a sentence
        or an empty string there.
         */
        Set<Integer> cache = new HashSet<>();

        StringBuilder sb = canBreak(text, 0, words, cache);

        //delete the extra whitespace char we might have added
        if(sb.length() > 0 && sb.charAt(sb.length() - 1) == ' '){
            sb.deleteCharAt(sb.length() - 1);
        }

        return sb.toString();
    }

    private static int subsetOfSumK(int target, int[] numbers, int index, Set<Pair<Integer, Integer>> seen, Stack<Integer> sol){
        //no elements left and we did not reach the target
        if(index >= numbers.length){
            return -1;
        }

        //reached the target, notify callers and stop
        if(target == 0){
            return 0;
        }

        //if we've already seen this pair (target, index), we did not find a solution from there, so stop
        //otherwise track as visited and process it
        Pair<Integer, Integer> curr = new Pair(target, index);

        if(seen.contains(curr)){
            return -1;
        }

        seen.add(curr);

        //for each element in range index..N-1 subtract from target and progress with the exploration on other elements
        for(int i = index; i < numbers.length; i++){
            int newTarget = target - numbers[i];

            Pair<Integer, Integer> currTarget = new Pair(newTarget, i);

            //if we've seen this pair(target, index), no need to try again, skip
            if(seen.contains(currTarget)){
                continue;
            }
            //otherwise track we're exploring this and proceed
            seen.add(currTarget);

            //add ourselves to the current solution stack
            sol.push(numbers[i]);

            //if we've reach the target, notify callers and stop
            if(newTarget == 0){
                return 0;
            }

            //otherwise only progress on positive targets (negative means goal was overshot)
            if(newTarget > 0){
                //recurse here, then check if this reached the target and in case, notify callers and stop
                int res = subsetOfSumK(newTarget, numbers, i + 1, seen, sol);

                if(res == 0){
                    return 0;
                }
            }

            //we did not reach the target, we are not part of the solution, remove us from solution stack
            sol.pop();

        }

        //if we arrived here, definitely we haven't reached the target
        return -1;
    }

    /**
     * Given an array of positive integers with possible duplicates, find a subset of elements whose sum is a given target.
     * @param target the target sum.
     * @param numbers the input elements.
     * @return a subset whose sum is the given target.
     */
    public static List<Integer> subsetOfSumK(int target, int... numbers){
        List<Integer> out = new ArrayList<>();

        if(numbers == null || numbers.length == 0){
            return out;
        }

        //visited tracks pairs of target,index
        //if we ever see the same pair again, it means we did not reach a solution from it and we can skip it
        Set<Pair<Integer, Integer>> seen = new HashSet<>();
        //we need to track which elements compose a possible solution
        //keep adding to a stack, if we reach the target the stack has all elements composing the solution
        //otherwise when backtracking (returning from call), it means current element is not in the solution
        //we therefore pop it and continue
        Stack<Integer> sol = new Stack<>();

        //start from target and first element, check if we can find a subset with that target
        int res = subsetOfSumK(target, numbers, 0, seen, sol);

        //if we reached the target, get all elements from the stack and add to the solution
        if(res == 0){
            for(Integer i : sol){
                out.add(i);
            }
        }

        return out;
    }

    //helper for nQueens
    //checks if we can place a queen on this board in the given (row,col) cell
    //we need to check from PREVIOUS rows, otherwise we count ourselves too
    private static boolean canPlaceQueen(boolean[][] board, int row, int col){
        //check if on same col in previous row there's already a queen
        int i = row - 1;
        int j = col;
        while(i >= 0){
            if(board[i][j]){
                return false;
            }
            i--;
        }

        //check if on \ diagonal there's already a queen
        i = row - 1;
        j = col - 1;
        while(i >= 0 && j >= 0){
            if(board[i][j]){
                return false;
            }
            i--;
            j--;
        }

        //check if on / diagonal there's already a queen
        i = row - 1;
        j = col + 1;
        while(i >= 0 && j < board.length){
            if(board[i][j]){
                return false;
            }
            i--;
            j++;
        }

        return true;
    }

    //helper for nQueens
    private static void placeQueens(boolean[][] board, int row, Stack<Pair<Integer,Integer>> placement, List<List<Pair<Integer,Integer>>> placements){
        //if we are at row N, it means we could place the last queen on the board successfully
        //and are now off the board so track the result and stop
        if(row == board.length){
            List<Pair<Integer,Integer>> out = new ArrayList<>(board.length);

            for(Pair<Integer,Integer> p : placement){
                out.add(p);
            }

            placements.add(out);

            return;
        }

        //otherwise we placed some queens at an earlier point, check every position in our row
        //for valid placement and recurse from there
        for(int j = 0; j < board.length; j++){
            //check earlier positions if any queen blocks us
            if(canPlaceQueen(board, row, j)){
                //place ourselves in this cell and move to next row
                board[row][j] = true;
                //track our position, could be part of the solution
                placement.push(new Pair<>(row, j));

                placeQueens(board, row + 1, placement, placements);

                //remove ourselves from this cell and check another position on this row
                board[row][j] = false;
                //remove us from possible solution
                placement.pop();
            }
        }
    }

    /**
     * Given a NxN board and N queens, count how many placements exist where no queen blocks another.
     * @param n the size of the board and number of queens.
     * @return how many placements there are where no queen blocks another.
     */
    public static int nQueens(int n){
        if(n <= 0){
            return 0;
        }

        //true if we placed a queen here
        boolean[][] board = new boolean[n][n];

        //starting from first row, we put a queen in every column
        //if that is a valid placement, we continue with the next row
        //if we ever reach the bottom row and successfully place a queen there we have a solution
        //all pairs of coordinates for a placement in a list, result is list of all placements
        List<List<Pair<Integer,Integer>>> placements = new ArrayList<>();
        Stack<Pair<Integer,Integer>> placement = new Stack<>();

        placeQueens(board, 0, placement, placements);

        //optional get positions looping over placements

        return placements.size();
    }

    //helper for regexMatch
    //checks if from this index in text and pattern we have a match
    static private boolean checkRegexMatch(String text, String pattern, int text_idx, int pattern_idx, boolean[][] cache){
        //reached end of text always matching pattern
        if(text_idx >= text.length() && pattern_idx >= pattern.length()){
            return true;
        }

        //reached end of text but not end of pattern, check if pattern is left with X* portions only where X is either char or dot
        if(text_idx >= text.length() && pattern_idx < pattern.length()){

            //if we don't have a next char, there is no *
            int p_idx = pattern_idx;

            while(p_idx < pattern.length()){
                //if next is not *, no match
                if(p_idx + 1 >= pattern.length() || pattern.charAt(p_idx + 1) != '*'){
                    return false;
                }
                //move to next char after *
                p_idx += 2;
            }

            return true;
        }

        //reach end of pattern but not of string
        if(pattern_idx >= pattern.length() && text_idx < text.length()){
            return false;
        }

        //already tried matching from this pair of text char and pattern char and failed, no point in trying again
        if(!cache[text_idx][pattern_idx]){
            return false;
        }

        //try matching current text char with current pattern
        char c = text.charAt(text_idx);
        char p = pattern.charAt(pattern_idx);
        //check if we have a * pattern
        boolean hasStar = false;

        if(pattern_idx + 1 < pattern.length() && pattern.charAt(pattern_idx + 1) == '*'){
            hasStar = true;
        }

        if(hasStar){
            //match this char and continue to next char with same pattern
            if(c == p || p == '.'){
                if(checkRegexMatch(text, pattern, text_idx + 1, pattern_idx, cache)){
                    return true;
                }
            }

            //skip this pattern and move to next pattern with same char
            if(checkRegexMatch(text, pattern, text_idx, pattern_idx + 2, cache)){
                return true;
            }
        }
        else{
            //match this char and continue if match is ok
            if(p == '.' || p == c){
                if(checkRegexMatch(text, pattern, text_idx + 1, pattern_idx + 1, cache)){
                    return true;
                }
            }
        }

        //we failed to find a match from this pair of text index and char index, track it and return failure
        cache[text_idx][pattern_idx] = false;
        return false;

    }

    /**
     * Given a simplified regex that allows characters, dots and stars, find if a given string matches a given pattern.
     * . = any char
     * * = 0 or more repetitions of previous char
     * @param text the text.
     * @param pattern the pattern to match.
     * @return true if text matches the pattern.
     */
    public static boolean regexMatch(String text, String pattern) {
        if(text == null || pattern == null){
            return false;
        }

        //cache if for a given combination of index in text and pattern we've already found a failure
        //so we can skip checking again if we go back there
        //this only happens when pattern contains special char *
        //false indicates we failed
        boolean[][] cache = new boolean[text.length()][pattern.length()];

        for(int i = 0; i < cache.length; i++){
            for(int j = 0; j < cache[0].length; j++){
                cache[i][j] = true;
            }
        }

        //start match from first char of both text and pattern
        return checkRegexMatch(text, pattern, 0, 0, cache);
    }

    /**
     * Given an array of integers, find the longest increasing subsequence and return it.
     * @param numbers the input numbers.
     * @return the elements composing the last found longest increasing subsequence.
     */
    public static List<Integer> longestIncreasingSubsequence(int... numbers){
        LinkedList<Integer> out = new LinkedList<>();

        if(numbers == null || numbers.length == 0){
            return out;
        }

        //Fredman-Knuth variant, also overlaps with patience sorting

        //predecessor[i] = INDEX of PREVIOUS element part of the longest subsequence ending at element in position i
        int[] predecessor = new int[numbers.length];
        //minIndexAtLength[i] = INDEX of the SMALLEST LAST element of the latest found longest subsequence of length i
        //since indices here are lengths, we have N+1 elements in this array
        //first index (length 0) has value -1 since we do not pick any element to form a subsequence of length 0
        int[] minIndexAtLength = new int[numbers.length + 1];
        minIndexAtLength[0] = -1;

        //current longest subsequence
        int maxLength = 0;

        //walk the array left to right
        for(int i = 0; i < numbers.length; i++){

            /*
            if the current element can improve on the longest subsequence so far, let's add it and continue
            minIndexAtLength[maxLength] >= 0: if this is not the case, there is no longest subsequence (we are the first element in the array)
            otherwise minIndexAtLength[maxLength] returns the INDEX of the SMALLEST LAST element in the current longest subsequence
            if we are bigger than that element, we can extend it
             */
            if(minIndexAtLength[maxLength] >= 0 && numbers[i] > numbers[minIndexAtLength[maxLength]]){
                //set our predecessor to the INDEX of SMALLEST LAST element in the current longest subsequence
                predecessor[i] = minIndexAtLength[maxLength];
                //expand the current longest subsequence
                maxLength++;
                //we are the INDEX of SMALLEST LAST element in NEW longest subsequence that includes us
                minIndexAtLength[maxLength] = i;
                //can skip the binary search logic in this case
                continue;
            }

            /*
            if the current element cannot improve on the longest subsequence so far
            maybe it can improve some other previous subsequence, start a new subsequence or offer a better choice
            for the SMALLEST LAST element of the current subsequence,
            we need to find the longest of those we can be used to improve upon.

            minIndexAtLength[i] tracks INDEX of SMALLEST LAST element for longest subsequence of length i
            this means minIndexAtLength[0] < minIndexAtLength[1] < ... < minIndexAtLength[i]
            which also means the elements pointed at by those indices are sorted increasing

            we search for the longest subsequence we can improve by adding ourselves
            which means searching for an UPPER bound, that is the SMALLEST LAST element of a longest subsequence
            that is bigger than us in order to replace it and therefore allow
            more possibilities to expand on that subsequence in the future

            example:

            1,2,5,3,4,5

            when we get to 3 the longest subsequence is 1,2,5 and we can't improve it by adding ourselves
            however, by replacing 5 with 3, we allow more values in the next part of the array to join the longest
            subsequence until there

            other example:

            1,2,10,11,3,4,5,6

            when we get to 3, we can't improve 1,2,10,11 and we also cannot replace 11 as the previous element is 10
            we could however be used instead of the portion 10,11 if at any point other elements bigger than 3 but smaller
            than 10 appear, leading to a longer subsequence
            so we track that by setting the index of LAST element of a sequence of length 3 to be us instead of 10 as
            it currently was.
            the longest subsequence is still 4

            when 4 arrives, we repeat the process but the longest subsequence is still of length 4 however the
            sequence 1,2,10,11 is now completely replaced by 1,2,3,4

            when 5 arrives, we realize this approach paid off as we can now expand the current subsequence by adding it
             */

            //binary search is in the range 1..maxLength as we're looking for the longest subsequence
            //where the LAST element is bigger than us, we want to replace it with ourselves
            //floor = 1 as worst case, we replace a subsequence of length 1 as we might be the start of a new
            //longest subsequence from this point in the array
            int floor = 1;
            int ceil = maxLength;

            while(floor <= ceil){
                int mid = floor + (ceil - floor) / 2;

                if(numbers[minIndexAtLength[mid]] < numbers[i]){
                    floor = mid + 1;
                }
                else{
                    ceil = mid - 1;
                }
            }

            //floor is now the length of the longest subsequence where we would be the last element
            //could be we didn't replace any element and just expanded on the current longest
            int newLength = floor;

            //set our predecessor to the predecessor of the shorter length than our current one
            predecessor[i] = minIndexAtLength[newLength - 1];
            //set ourselves as the index of the SMALLEST LAST element of the subsequence of this length
            minIndexAtLength[newLength] = i;

            //in case we improved on the current subsequence, track it
            if(newLength > maxLength){
                maxLength = newLength;
            }
        }

        //now we backtrack to reconstruct the longest subsequence, we start from the last element
        //if there are multiple subsequence of same length, we consider the latest found one
        //get the INDEX of LAST element of longest subsequence
        int k = minIndexAtLength[maxLength];

        //walking backwards, pick all elements BEFORE us
        //they are the LAST elements of a subsequence which always gets shorter by 1
        //since we started from the last, add each element to the head of the list so we have
        //the increasing and not decreasing subsequence
        for(int i = maxLength - 1; i >= 0; i--){
            out.addFirst(numbers[k]);
            k = predecessor[k];
        }

        return out;
    }

    /**
     * Given an array of numbers, find 3 distinct elements that appear after each other so that i < j < k.
     * @param numbers the input numbers.
     * @return the first triple of elements that satisfy the condition i < j < k where each element appears before the next
     * appearing in the last found longest increasing subsequence.
     */
    public static List<Integer> increasingSubtriple(int... numbers){
        List<Integer> res = new ArrayList<>();

        if(numbers == null || numbers.length < 3){
            return res;
        }

        /*
        This is simply the longest increasing subsequence of length 3.
        If the longest subsequence is shorter than 3, there is no answer,
        otherwise we take the first three elements of that sequence as answer.
        We could take any three consecutive elements in that list.
         */
        List<Integer> out = longestIncreasingSubsequence(numbers);

        if(out.size() < 3){
            return res;
        }

        //output of longestIncreasingSubsequence is linked list
        //better if we walk on that to avoid repeated scans from start to get ith element, even if it's only 3
        for(int i : out){
            if(res.size() == 3){
                break;
            }
            res.add(i);
        }

        return res;
    }
}

IncreasingSubtripleJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class IncreasingSubtripleJTests {

    int[] in;
    List<Integer> out, expected;

    @Test
    public void nullEmpty() {
        in = null;
        out = DPUtils.increasingSubtriple(in);
        assertTrue("null", out.isEmpty());

        in = new int[]{};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("empty", out.isEmpty());
    }

    @Test
    public void tooFew() {
        in = new int[]{1,2};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("1,2", out.isEmpty());
    }

    @Test
    public void allSame() {
        in = new int[]{1,1,1,1};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("1,1,1,1", out.isEmpty());
    }

    @Test
    public void decreasing() {
        in = new int[]{5,4,3,2,1};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("5,4,3,2,1", out.isEmpty());
    }

    @Test
    public void invertedTriangle() {
        in = new int[]{5,4,3,5,5};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("5,4,3,5,5", out.isEmpty());

        in = new int[]{5,4,3,4,5};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(3);
        expected.add(4);
        expected.add(5);
        assertEquals("5,4,3,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void increasing() {
        in = new int[]{1,2,3,4,5};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(1);
        expected.add(2);
        expected.add(3);
        assertEquals("1,2,3,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void triangle() {
        in = new int[]{1,2,1,2,1};
        out = DPUtils.increasingSubtriple(in);
        assertTrue("1,2,1,2,1", out.isEmpty());

        in = new int[]{1,2,1,3};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(1);
        expected.add(2);
        expected.add(3);
        assertEquals("1,2,1,3", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{1,2,100,4,5};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(1);
        expected.add(2);
        expected.add(4);
        assertEquals("1,2,100,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void sample() {
        in = new int[]{2,1,5,0,4,6};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(0);
        expected.add(4);
        expected.add(6);
        assertEquals("2,1,5,0,4,6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{1,5,0,6};
        out = DPUtils.increasingSubtriple(in);
        expected = new ArrayList<>(3);
        expected.add(1);
        expected.add(5);
        expected.add(6);
        assertEquals("1,5,0,6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }
}

IntWrapper.java

package com.blogspot.groglogs.structures;

/**
 * A wrapper on integers, useful for tracking and updating int values during recursion.
 */
public class IntWrapper {
    private int val;

    public IntWrapper(int start){
        this.val = start;
    }

    public void addVal(int val){
        this.val += val;
    }

    public int getVal(){
        return this.val;
    }
}

Item.java

package com.blogspot.groglogs.knapsack.structures;

import java.util.Objects;

public class Item{
    public String label;
    public int weight, value, q;

    public Item(String label, int weight, int value){
        this.label = label;
        this.weight = weight;
        this.value = value;
        this.q = 0;
    }

    @Override
    public boolean equals(Object o) {

        if (o == this) return true;
        if (!(o instanceof Item)) {
            return false;
        }
        Item item = (Item) o;
        return this.label.equals(item.label)
                && this.weight == item.weight
                && this.value == item.value
                ;
    }

    @Override
    public int hashCode() {
        return Objects.hash(label, weight, value);
    }
}

ItemComparator.java

package com.blogspot.groglogs.knapsack.helpers;

import com.blogspot.groglogs.knapsack.structures.Item;

import java.util.Comparator;

public class ItemComparator implements Comparator<Item> {
    @Override
        /*
        sort items based on descending value
        if q_value is same, based on ascending weight
         */
    public int compare(Item i1, Item i2) {
        //same label means same item
        if(i1.label == i2.label) return 0;

            /*
            otherwise, sort by q_value first and if value is same, by weight
            since we want descending order, return values are inverted
            */
        if(i1.q < i2.q) return 1;
        if(i1.q > i2.q) return -1;

        if(i1.weight <= i2.weight) return 1;
        return -1;
    }
}

Knapsack.java

package com.blogspot.groglogs.knapsack;

import java.util.*;

import com.blogspot.groglogs.knapsack.structures.*;
import com.blogspot.groglogs.knapsack.helpers.*;

public class Knapsack {

    public static Result fillKnapsack(List<Item> items, int max_weight){
        Result res = null;

        /*
        will track temporary data in two steps.
        1- for each item how much space would be left if it was picked
        for later calculation purposes, if space left is 0 we store 1 instead
        2- calculate how much value gain we get by selecting this element based on its value
        and on the space it leaves
        */
        int left;
        Item it;


        //no such bag exists or no items in the list or wrong lists
        if(max_weight <= 0 || items == null || items.size() == 0)return res;

        /*
        compute for each item how much space it would leave
        and how much gain would we have by selecting it based on the space left
        a negative value means the item does not fit in the bag
        */
        for(int i = 0; i < items.size(); i++){
            if(items.get(i).weight < 0) items.get(i).q = -1;
            else {
                left = max_weight - items.get(i).weight;
                //for calculation purposes we convert 0 to 1
                left = (left == 0) ? 1 : left;

                items.get(i).q = items.get(i).value * left;
            }
        }

        //sort the value_weight by descending q_value order and ascending weight order if q_value is same
        Collections.sort(items, new ItemComparator());

        /*
        start filling up the knapsack. Begin by putting with first item in value_weight and decrease the space left
        if an item does not fit, skip it
        if we find a <= 0 q_value, stop because all items from here on are bigger than the bag or 0 valued
        */
        res = new Result();
        Iterator iter = items.iterator();
        left = max_weight;

        //keep going until we have no more items or space left. Stop if we have <= 0 q_values
        while(left > 0 && iter.hasNext()){
            it = (Item) iter.next();

            if(it.q <= 0) break;

            if(it.weight <= left) {
                res.addResultItem(it.label, it.weight, it.value);
                left -= it.weight;
            }
        }

        return res;
    }

    //determine the optimal answer considering that each item can be chosen an infinite number of times
    public static Result fillUnboundedKnapsack(List<Item> items, int max_weight){
        //no such bag exists or no items in the list or wrong lists
        if(max_weight <= 0 || items == null || items.size() == 0) throw new IllegalArgumentException("Items cannot be empty and bag cannot hold less than 1 weight!");

        //for each increment in bag capacity, track the maximum value we can carry
        //empty bag means 0 max value, we track it for calculation but raise an exception if input capacity is <= 0
        Result[] maxValueForWeight = new Result[max_weight + 1];
        maxValueForWeight[0] = new Result(new LinkedList<>(), 0, 0);

        Result currMaxForWeight, valueWithItem;
        
        //cleanup the items, if we can't include some, remove them
        //@todo further compare items and test if an item weighs more and has less value than another, it will NEVER be chosen!
        Iterator<Item> itemIterator = items.iterator();
        while(itemIterator.hasNext()){
            Item item = itemIterator.next();
            if(item.weight > max_weight) itemIterator.remove();
        }

        //maybe we removed all potential items
        if(items.isEmpty()) return new Result();

        //build up our knowledge until we reach the maximum capacity
        for(int currWeight = 1; currWeight <= max_weight; currWeight++) {
            currMaxForWeight = new Result(new LinkedList<>(), 0, 0);

            //consider all the items each time
            for (Item item : items) {
                valueWithItem = new Result(new LinkedList<>(), 0, 0);

                if (item.weight <= 0 || item.value < 0)
                    throw new IllegalArgumentException("Items cannot have negative value or weight <= 0!");

                //as long as we can currently consider the item, check whether it's better to pick only that
                //or pick it considering we can also pick more items with lesser weight up to the current weight
                //remember to track which other items we are picking as well in case!
                if(item.weight <= currWeight){
                    valueWithItem = new Result(null, currWeight, item.value + maxValueForWeight[currWeight - item.weight].value); //can't fail because item.weight <= currWeight
                    List<Item> currItems = new LinkedList<>();
                    currItems.addAll(maxValueForWeight[currWeight - item.weight].itemsList);
                    currItems.add(item);
                    valueWithItem.itemsList = currItems;
                }

                //better to keep the item alone or consider more items together?
                if(valueWithItem.value > currMaxForWeight.value) currMaxForWeight = valueWithItem;

            }

            maxValueForWeight[currWeight] = currMaxForWeight;
        }

        //collect the output nicely, group repeated items and count how many times they are picked
        HashMap<Item, Integer> pickedItems = new HashMap<>();
        for(Item item : maxValueForWeight[max_weight].itemsList){
            Integer count = pickedItems.get(item);
            count = (count != null) ? count + 1 : 1;
            pickedItems.put(item, count);
        }

        List<Item> outItems = new LinkedList<>();

        for(Item item : pickedItems.keySet()){
            item.q = pickedItems.get(item);
            outItems.add(item);
        }

        maxValueForWeight[max_weight].itemsList = outItems;

        return maxValueForWeight[max_weight];

    }

    //helper for fillKnapsackDP to generate the result list
    //to find which elements we actually chose, we start from the last cell and backtrack
    //if the element in the cell we are considering is actually different from the one computed at the previous pick
    //it means it's part of the result set and the next one should be searched for in the remaining weight excluding it
    //otherwise, keep walking back for the current weight
    private static void findKnapsackDPItem(int[][] picks, Result res, List<Item> items, int item, int weight){
        if(item == 0) return;
        //if we picked this item, add it to the result set and search for the item we picked before it
        //that would be the best item in the remaining weight after we took the current one out
        if(picks[item][weight] > picks[item - 1][weight]){
            Item i = items.get(item - 1); //0-based index in list but NOT in cache!
            res.addResultItem(i.label, i.weight, i.value);
            findKnapsackDPItem(picks, res, items, item - 1, weight - i.weight);
        } else{
        //otherwise we actually did not pick it, so keep searching for the best one we picked previously up to this weight
          findKnapsackDPItem(picks, res, items, item - 1, weight);
        }
    }

    public static Result getKnapsackDP(int[][] picks, List<Item> items, int max_weight){
        Result res = new Result();

        findKnapsackDPItem(picks, res, items, items.size(), max_weight);

        return res;
    }

    //prints the computed cache
    private static void printDPCache(int[][] picks){
        System.out.println("cache is:");
        System.out.print("w:   ");
        for(int j = 0; j < picks[0].length; j++){
            System.out.print(j + " ");
        }
        System.out.println();
        for(int i = 0; i < picks.length; i++){
            System.out.print("[" + i + "]: ");
            for(int j = 0; j < picks[0].length; j++){
                System.out.print(picks[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static Result fillKnapsackDP(List<Item> items, int max_weight){
        //no such bag exists or no items in the list or wrong lists
        if(max_weight <= 0 || items == null || items.size() == 0) throw new IllegalArgumentException("Items cannot be empty and bag cannot hold less than 1 weight!");

        //number of items picked, weight of the item
        //0-based index! We use 0 row as base and go all the way up to the actual values, so size + 1
        int[][] picks = new int[items.size() + 1][max_weight + 1];

        //initialize cache. No items picked will never impact the weight
        for(int weight = 0; weight <= max_weight; weight++) picks[0][weight] = 0;

        //compute the best pick combination
        //for each item we have, determine which combination is best for each bag capacity up to our weight limit
        for(int item = 1; item <= items.size(); item++){
            for(int weight = 0; weight <= max_weight; weight++){
                //index is 0 based
                int w = items.get(item - 1).weight;
                int v = items.get(item - 1).value;
                //if this item weighs too much, we can only keep the previous best item also for this weight slot
                if(w > weight){
                    picks[item][weight] = picks[item - 1][weight];
                } else {
                    //otherwise we must choose whether the previous best item for this weight slot is better than
                    //the current item plus, if any, the other best item we can also pick trying to fill
                    //the remaining space up to the current limit
                    picks[item][weight] = Math.max(picks[item - 1][weight], picks[item - 1][weight - w] + v);
                }
            }
        }

        Result res = getKnapsackDP(picks, items, max_weight);

        //printDPCache(picks);

        return res;

    }
}

KnapsackJTests.java

package com.blogspot.groglogs.test.knapsack;

import org.junit.Test;
import com.blogspot.groglogs.knapsack.Knapsack;
import com.blogspot.groglogs.knapsack.structures.*;

import java.util.*;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class KnapsackJTests {

    List<String> output;
    Result res, out;
    List<Item> input, outList;
    int max_weight;

    @Test
    //null or empty input, expected null
    public void nullEmpty() {
        input  = null;
        output = null;
        max_weight = 1;

        //null
        assertEquals("null = null", output, Knapsack.fillKnapsack(input, max_weight));

        try{
            res = Knapsack.fillKnapsackDP(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("null input for DP got IllegalArgumentException " + e.getMessage());
        }

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("null input got IllegalArgumentException " + e.getMessage());
        }

        input  = new ArrayList<>();
        max_weight = 1;

        //empty
        assertEquals("empty = null", output, Knapsack.fillKnapsack(input, max_weight));

        try{
            res = Knapsack.fillKnapsackDP(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("empty input for DP got IllegalArgumentException " + e.getMessage());
        }

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("empty input got IllegalArgumentException " + e.getMessage());
        }
    }

    @Test
    //<= 0 max size
    public void badSize() {
        output = null;
        input  = new ArrayList<>();
        input.add(new Item("A", 1, 1));
        max_weight = 0;

        //0 max size
        assertEquals("0 size = null", output, Knapsack.fillKnapsack(input, max_weight));

        try{
            res = Knapsack.fillKnapsackDP(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("0 bag size for DP got IllegalArgumentException " + e.getMessage());
        }

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("0 bag size got IllegalArgumentException " + e.getMessage());
        }

        max_weight = -1;

        //negative max size
        assertEquals("negative size = null", output, Knapsack.fillKnapsack(input, max_weight));

        try{
            res = Knapsack.fillKnapsackDP(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("negative bag size for DP got IllegalArgumentException " + e.getMessage());
        }

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("negative bag size got IllegalArgumentException " + e.getMessage());
        }
    }

    @Test
    //negative item values
    public void itemNegValues() {
        output = new ArrayList<>();
        input  = new ArrayList<>();
        input.add(new Item("A", 1, -1));
        max_weight = 10;

        assertEquals("item negative value = empty", output, Knapsack.fillKnapsack(input, max_weight).items);

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("negative item value got IllegalArgumentException " + e.getMessage());
        }
    }

    @Test
    //negative item weights
    public void itemNegWeights() {
        output = new ArrayList<>();
        input  = new ArrayList<>();
        input.add(new Item("A", -1, 1));
        max_weight = 10;

        assertEquals("item negative weight = empty", output, Knapsack.fillKnapsack(input, max_weight).items);

        try{
            res = Knapsack.fillUnboundedKnapsack(input, max_weight);
        }catch(IllegalArgumentException e){
            System.out.println("negative item weight got IllegalArgumentException " + e.getMessage());
        }
    }

    @Test
    //only positive weights and values
    public void itemAllPos() {
        input = new ArrayList<>();
        input.add(new Item("A", 1, 8));
        input.add(new Item("B", 2, 4));
        input.add(new Item("C", 3, 0));
        input.add(new Item("D", 2, 5));
        input.add(new Item("E", 2, 3));
        max_weight = 4;

        output = new ArrayList<>();
        output.add("A");
        output.add("D");

        res = new Result();
        res.items = output;
        res.value = 13;
        res.weight = 3;

        assertEquals("all positive items = A,D", res.items, Knapsack.fillKnapsack(input, max_weight).items);
        assertEquals("all positive items value = 13", res.value, Knapsack.fillKnapsack(input, max_weight).value);
        assertEquals("all positive items weight = 3", res.weight, Knapsack.fillKnapsack(input, max_weight).weight);

        //DP
        output = new ArrayList<>();
        output.add("D");
        output.add("A");

        res = new Result();
        res.items = output;
        res.value = 13;
        res.weight = 3;

        assertEquals("all positive items DP = D,A", res.items, Knapsack.fillKnapsackDP(input, max_weight).items);
        assertEquals("all positive items DP value = 13", res.value, Knapsack.fillKnapsackDP(input, max_weight).value);
        assertEquals("all positive items DP weight = 3", res.weight, Knapsack.fillKnapsackDP(input, max_weight).weight);

        input = new ArrayList<>();
        input.add(new Item("A", 2, 3));
        input.add(new Item("B", 3, 4));
        input.add(new Item("C", 4, 5));
        input.add(new Item("D", 5, 6));
        max_weight = 5;

        output = new ArrayList<>();
        output.add("A");
        output.add("B");

        res = new Result();
        res.items = output;
        res.value = 7;
        res.weight = 5;

        assertEquals("all positive items = A,B", res.items, Knapsack.fillKnapsack(input, max_weight).items);
        assertEquals("all positive items value = 7", res.value, Knapsack.fillKnapsack(input, max_weight).value);
        assertEquals("all positive items weight = 5", res.weight, Knapsack.fillKnapsack(input, max_weight).weight);

        //DP
        output = new ArrayList<>();
        output.add("B");
        output.add("A");

        res = new Result();
        res.items = output;
        res.value = 7;
        res.weight = 5;

        assertEquals("all positive items DP = B,A", res.items, Knapsack.fillKnapsackDP(input, max_weight).items);
        assertEquals("all positive items DP value = 7", res.value, Knapsack.fillKnapsackDP(input, max_weight).value);
        assertEquals("all positive items DP weight = 5", res.weight, Knapsack.fillKnapsackDP(input, max_weight).weight);

        input = new ArrayList<>();
        input.add(new Item("A", 1, 1));
        input.add(new Item("B", 3, 4));
        input.add(new Item("C", 4, 5));
        input.add(new Item("D", 5, 7));
        max_weight = 7;

        output = new ArrayList<>();
        output.add("B");
        output.add("C");

        res = new Result();
        res.items = output;
        res.value = 9;
        res.weight = 7;

        assertEquals("all positive items = B,C", res.items, Knapsack.fillKnapsack(input, max_weight).items);
        assertEquals("all positive items value = 9", res.value, Knapsack.fillKnapsack(input, max_weight).value);
        assertEquals("all positive items weight = 5", res.weight, Knapsack.fillKnapsack(input, max_weight).weight);

        //DP
        output = new ArrayList<>();
        output.add("C");
        output.add("B");

        res = new Result();
        res.items = output;
        res.value = 9;
        res.weight = 7;

        assertEquals("all positive items DP = C,B", res.items, Knapsack.fillKnapsackDP(input, max_weight).items);
        assertEquals("all positive items DP value = 9", res.value, Knapsack.fillKnapsackDP(input, max_weight).value);
        assertEquals("all positive items DP weight = 5", res.weight, Knapsack.fillKnapsackDP(input, max_weight).weight);

        input = new ArrayList<>();
        Item a, b, c;
        a = new Item("A", 7, 160);
        input.add(a);
        b = new Item("B", 3, 90);
        input.add(b);
        c = new Item("C", 2, 15);
        input.add(c);
        max_weight = 20;

        outList = new ArrayList<>();
        b.q = 6;
        outList.add(b);
        c.q = 1;
        outList.add(c);

        res = new Result();
        res.itemsList = outList;
        res.value = 555;
        res.weight = 20;

        out = Knapsack.fillUnboundedKnapsack(input, max_weight);

        assertArrayEquals("unbounded knapsack items B:6, C:1", res.itemsList.toArray(), out.itemsList.toArray());
        assertEquals("unbounded knapsack value = 555", res.value, out.value);
        assertEquals("unbounded knapsack weight = 20", res.weight, out.weight);

        input = new ArrayList<>();
        a = new Item("A", 7, 160);
        input.add(a);
        b = new Item("B", 3, 90);
        input.add(b);
        c = new Item("C", 2, 15);
        input.add(c);
        max_weight = 1;

        res = new Result();
        res.itemsList = new ArrayList<>();
        res.value = 0;
        res.weight = 0;

        out = Knapsack.fillUnboundedKnapsack(input, max_weight);

        assertArrayEquals("unbounded knapsack no item items empty", res.itemsList.toArray(), out.itemsList.toArray());
        assertEquals("unbounded knapsack no item value = 0", res.value, out.value);
        assertEquals("unbounded knapsack no item weight = 0", res.weight, out.weight);
    }

    @Test
    //heuristic fails
    public void heuristicFails() {
        input = new ArrayList<>();
        input.add(new Item("A", 3, 5));
        input.add(new Item("B", 2, 3));
        max_weight = 4;

        output = new ArrayList<>();
        output.add("B");//should be A instead!

        res = new Result();
        res.items = output;
        res.value = 3;
        res.weight = 2;

        assertEquals("heuristic fail = B, should be A", res.items, Knapsack.fillKnapsack(input, max_weight).items);
        assertEquals("heuristic fail value = 3, should be 5", res.value, Knapsack.fillKnapsack(input, max_weight).value);
        assertEquals("heuristic fail weight = 2, should be 3", res.weight, Knapsack.fillKnapsack(input, max_weight).weight);
    }

    @Test
    //DP does not fail
    public void DPnotFails() {
        input = new ArrayList<>();
        input.add(new Item("A", 3, 5));
        input.add(new Item("B", 2, 3));
        max_weight = 4;

        output = new ArrayList<>();
        output.add("A");

        res = new Result();
        res.items = output;
        res.value = 5;
        res.weight = 3;

        assertEquals("DP does not fail = A", res.items, Knapsack.fillKnapsackDP(input, max_weight).items);
        assertEquals("DP does not fail value = 5", res.value, Knapsack.fillKnapsackDP(input, max_weight).value);
        assertEquals("DP does not fail weight = 3", res.weight, Knapsack.fillKnapsackDP(input, max_weight).weight);

        input = new ArrayList<>();
        input.add(new Item("A", 12, 3));
        input.add(new Item("B", 15, 8));
        input.add(new Item("C", 16, 9));
        input.add(new Item("D", 16, 6));
        input.add(new Item("E", 10, 2));
        input.add(new Item("F", 21, 9));
        input.add(new Item("G", 18, 4));
        input.add(new Item("H", 12, 4));
        input.add(new Item("I", 17, 8));
        input.add(new Item("J", 18, 9));
        max_weight = 50;

        output = new ArrayList<>();
        output.add("J");
        output.add("C");
        output.add("B");

        res = new Result();
        res.items = output;
        res.value = 26;
        res.weight = 49;

        assertEquals("DP does not fail = J,C,B", res.items, Knapsack.fillKnapsackDP(input, max_weight).items);
        assertEquals("DP does not fail value = 26", res.value, Knapsack.fillKnapsackDP(input, max_weight).value);
        assertEquals("DP does not fail weight = 49", res.weight, Knapsack.fillKnapsackDP(input, max_weight).weight);
    }
}

LongestCommonSubsequenceJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class LongestCommonSubsequenceJTests {
    String a, b;
    String expected;

    @Test
    public void nullEmpty() {
        a = null;
        b = null;
        expected = "";
        assertEquals("null", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("null string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "";
        b = "asd";
        expected = "";
        assertEquals("empty", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("empty string", expected, DPUtils.longestCommonSubsequenceString(a, b));
    }

    @Test
    public void sameString() {
        a = "asd";
        b = "asd";
        expected = a;
        assertEquals("same", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("same string", expected, DPUtils.longestCommonSubsequenceString(a, b));
    }

    @Test
    public void fullSubstring() {
        a = "asd";
        b = "lolasd";
        expected = a;
        assertEquals("full postfix substring", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("full postfix substring string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "asd";
        b = "asdlol";
        expected = a;
        assertEquals("full prefix substring", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("full prefix substring string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "asd";
        b = "aasdl";
        expected = a;
        assertEquals("full infix substring", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("full infix substring string", expected, DPUtils.longestCommonSubsequenceString(a, b));
    }

    @Test
    public void noMatch() {
        a = "asd";
        b = "lol";
        expected = "";
        assertEquals("no match", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("no match string", expected, DPUtils.longestCommonSubsequenceString(a, b));
    }

    @Test
    public void sample() {
        a = "aggtab";
        b = "gxtxayb";
        expected = "gtab";
        assertEquals("aggtab, gxtxayb", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("aggtab, gxtxayb string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "aggtab";
        b = "xtxayb";
        expected = "tab";
        assertEquals("aggtab, xtxayb", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("aggtab, xtxayb string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "lggtab";
        b = "xtxaybztab";
        expected = "tab";
        assertEquals("lggtab, xtxaybztab", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("lggtab, xtxaybztab string", expected, DPUtils.longestCommonSubsequenceString(a, b));

        a = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
        b = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
        expected = "GTCGTCGGAAGCCGGCCGAA";
        assertEquals("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, GTCGTTCGGAATGCCGTTGCTCTGTAAA", expected, DPUtils.longestCommonSubsequence(a, b));
        assertEquals("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, GTCGTTCGGAATGCCGTTGCTCTGTAAA string", expected, DPUtils.longestCommonSubsequenceString(a, b));
    }
}

LongestIncreasingSubsequenceJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class LongestIncreasingSubsequenceJTests {

    int[] in;
    List<Integer> out, expected;

    @Test
    public void nullEmpty() {
        in = null;
        out = DPUtils.longestIncreasingSubsequence(in);
        assertTrue("null", out.isEmpty());

        in = new int[]{};
        out = DPUtils.longestIncreasingSubsequence(in);
        assertTrue("empty", out.isEmpty());
    }

    @Test
    public void allSame() {
        in = new int[]{1,1,1,1};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        assertEquals("1,1,1,1", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void decreasing() {
        in = new int[]{5,4,3,2,1};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        assertEquals("5,4,3,2,1", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void invertedTriangle() {
        in = new int[]{5,4,3,5,5};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(3);
        expected.add(5);
        assertEquals("5,4,3,5,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{5,4,3,4,5};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(3);
        expected.add(4);
        expected.add(5);
        assertEquals("5,4,3,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void increasing() {
        in = new int[]{1,2,3,4,5};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(3);
        expected.add(4);
        expected.add(5);
        assertEquals("1,2,3,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void triangle() {
        in = new int[]{1,2,1,2,1};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        assertEquals("1,2,1,2,1", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{1,2,1,3};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(3);
        assertEquals("1,2,1,3", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{1,2,100,4,5};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(4);
        expected.add(5);
        assertEquals("1,2,100,4,5", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void sample() {
        in = new int[]{1,2,10,11,3,4,5,6};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(3);
        expected.add(4);
        expected.add(5);
        expected.add(6);
        assertEquals("1,2,10,11,3,4,5,6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{2,1,5,0,4,6};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(0);
        expected.add(4);
        expected.add(6);
        assertEquals("2,1,5,0,4,6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{1,5,0,6};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(5);
        expected.add(6);
        assertEquals("1,5,0,6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }

        in = new int[]{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
        out = DPUtils.longestIncreasingSubsequence(in);
        expected = new ArrayList<>();
        expected.add(0);
        expected.add(2);
        expected.add(6);
        expected.add(9);
        expected.add(11);
        expected.add(15);
        assertEquals("0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("element is correct", expected.get(i), out.get(i));
        }
    }
}

LongestPalindromicSubsequenceJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class LongestPalindromicSubsequenceJTests {
    String s;
    String expected;

    @Test
    public void nullEmpty() {
        s = null;
        expected = "";
        assertEquals("null", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "";
        expected = "";
        assertEquals("empty", expected, DPUtils.longestPalindromicSubsequence(s));
    }

    @Test
    public void wholeString() {
        s = "acca";
        expected = s;
        assertEquals("whole string", expected, DPUtils.longestPalindromicSubsequence(s));
    }

    @Test
    public void fullSubstring() {
        s = "aacca";
        expected = "acca";
        assertEquals("full postfix substring", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "accaa";
        expected = "acca";
        assertEquals("full prefix substring", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "laccam";
        expected = "acca";
        assertEquals("full infix substring", expected, DPUtils.longestPalindromicSubsequence(s));
    }

    @Test
    public void oddLengthPalindrome() {
        s = "aacbca";
        expected = "acbca";
        assertEquals("full postfix substring", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "acbcaa";
        expected = "acbca";
        assertEquals("full prefix substring", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "lacbcam";
        expected = "acbca";
        assertEquals("full infix substring", expected, DPUtils.longestPalindromicSubsequence(s));
    }

    @Test
    public void noPalindrome() {
        s = "asd";
        expected = "d";
        assertEquals("one letter is palindrome", expected, DPUtils.longestPalindromicSubsequence(s));
    }

    @Test
    public void sample() {
        s = "abdccklano";
        expected = "acca";
        assertEquals("abdccklano", expected, DPUtils.longestPalindromicSubsequence(s));

        s = "abdcfcklano";
        expected = "acfca";
        assertEquals("abdcfcklano", expected, DPUtils.longestPalindromicSubsequence(s));
    }
}

LongestWiggleSubsequenceJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class LongestWiggleSubsequenceJTests {

    int[] nums;
    int expected;

    @Test
    public void nullEmpty() {
        nums = null;
        expected = 0;
        assertEquals("null", expected, DPUtils.longestWiggleSubsequence(nums));

        nums = new int[]{};
        expected = 0;
        assertEquals("empty", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void oneElement() {
        nums = new int[]{1};
        expected = 1;
        assertEquals("1", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void twoElement() {
        nums = new int[]{1,2};
        expected = 2;
        assertEquals("1,2", expected, DPUtils.longestWiggleSubsequence(nums));

        nums = new int[]{2,1};
        expected = 2;
        assertEquals("2,1", expected, DPUtils.longestWiggleSubsequence(nums));

        nums = new int[]{1,1};
        expected = 1;
        assertEquals("1,1", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void increasing() {
        nums = new int[]{1,2,3,4,5};
        expected = 2;
        assertEquals("1,2,3,4,5", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void decreasing() {
        nums = new int[]{5,4,3,2,1};
        expected = 2;
        assertEquals("5,4,3,2,1", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void pyramid() {
        nums = new int[]{1,2,3,2,1};
        expected = 3;
        assertEquals("1,2,3,2,1", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void wholeSequence() {
        nums = new int[]{2,1,2,1,2};
        expected = nums.length;
        assertEquals("2,1,2,1,2", expected, DPUtils.longestWiggleSubsequence(nums));
    }

    @Test
    public void sample() {
        nums = new int[]{1,7,4,9,2,5};
        expected = nums.length;
        assertEquals("1,7,4,9,2,5", expected, DPUtils.longestWiggleSubsequence(nums));

        nums = new int[]{1,17,5,10,13,15,10,5,16,8};
        expected = 7;
        assertEquals("1,17,5,10,13,15,10,5,16,8", expected, DPUtils.longestWiggleSubsequence(nums));
    }
}

MaxRodCutProfitJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import com.blogspot.groglogs.structures.Pair;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertEquals;

public class MaxRodCutProfitJTests {

    int[] lengthProfits;
    int rodSize;
    Pair<Integer, List<Integer>> expected;

    @Test
    public void nullEmpty() {
        lengthProfits = null;
        rodSize = 1;
        expected = new Pair<>(-1, new ArrayList<>());
        assertEquals("null profits", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("null profits bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));

        lengthProfits = new int[]{};
        rodSize = 1;
        expected = new Pair<>(-1, new ArrayList<>());
        assertEquals("empty profits", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("empty profits bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));
    }

    @Test
    public void badInput() {
        lengthProfits = new int[]{1};
        rodSize = 0;
        expected = new Pair<>(-1, new ArrayList<>());
        assertEquals("zero rod size", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("zero rod size bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));

        lengthProfits = new int[]{1};
        rodSize = 10;
        expected = new Pair<>(-1, new ArrayList<>());
        assertEquals("rod size bigger than profits len", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("rod size bigger than profits len bottm", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));
    }

    @Test
    public void increasingProfit() {
        //better NOT to cut the rod
        lengthProfits = new int[]{1,2,3,4,7};
        rodSize = 5;
        ArrayList<Integer> cuts = new ArrayList<>();
        cuts.add(5);
        expected = new Pair<>(7, cuts);
        assertEquals("1,2,3,4,5 len 5", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("1,2,3,4,5 len 5 bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));
    }

    @Test
    public void decreasingProfit() {
        //better to cut the rod multiple times with smallest cut
        lengthProfits = new int[]{5,4,3,2,1};
        rodSize = 5;
        ArrayList<Integer> cuts = new ArrayList<>();
        cuts.add(1);
        cuts.add(1);
        cuts.add(1);
        cuts.add(1);
        cuts.add(1);
        expected = new Pair<>(25, cuts);
        assertEquals("5,4,3,2,1 len 5", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("5,4,3,2,1 len 5 bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));
    }

    @Test
    public void sample() {
        //length 4, best cut is 2,2 for total of 10
        lengthProfits = new int[]{1,5,8,9,10,17,17,20,24,30};
        rodSize = 4;
        ArrayList<Integer> cuts = new ArrayList<>();
        cuts.add(2);
        cuts.add(2);
        expected = new Pair<>(10, cuts);
        assertEquals("1,5,8,9,10,17,17,20,24,30 len 4", expected, DPUtils.maxRodCutProfitDP(lengthProfits, rodSize));
        assertEquals("1,5,8,9,10,17,17,20,24,30 len 4 bottom", expected, DPUtils.maxRodCutProfitDPBottomUp(lengthProfits, rodSize));
    }
}

MinCostToPaintHousesJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MinCostToPaintHousesJTests {

    int[][] costToPaintHouseWithColor;
    int expected;

    @Test
    public void nullEmpty() {
        costToPaintHouseWithColor = null;
        expected = -1;
        assertEquals("null costs", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));

        costToPaintHouseWithColor = new int[][]{};
        expected = -1;
        assertEquals("empty costs", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));

        costToPaintHouseWithColor = new int[][]{{}};
        expected = -1;
        assertEquals("array costs", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));
    }

    @Test
    public void notEnoughColors() {
        costToPaintHouseWithColor = new int[][]{{1},{2}};
        expected = -1;
        assertEquals("not enough colors", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));
    }

    @Test
    public void twoHousesTwoColors() {
        costToPaintHouseWithColor = new int[][]{
                {10, 1},
                {10, 1}
        };
        expected = 11;
        assertEquals("color 1 = 10, color 2 = 1, 2 houses", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));
    }

    @Test
    public void threeHousesTwoColors() {
        costToPaintHouseWithColor = new int[][]{
                {10, 1},
                {10, 1},
                {10, 1}
        };
        expected = 12;
        assertEquals("color 1 = 10, color 2 = 1, 3 houses", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));
    }

    @Test
    public void sample() {
        costToPaintHouseWithColor = new int[][]{
                {14, 2, 11},
                {11, 14, 5},
                {14, 3, 10}
        };
        expected = 10;
        assertEquals("sample", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));

        costToPaintHouseWithColor = new int[][]{
                {1, 2, 3},
                {1, 4, 6}
        };
        expected = 3;
        assertEquals("sample 2", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));

        costToPaintHouseWithColor = new int[][]{
                {1, 5, 7},
                {5, 8, 4},
                {3, 2, 9},
                {1, 2, 4}
        };
        expected = 8;
        assertEquals("sample 3", expected, DPUtils.minCostToPaintHouses(costToPaintHouseWithColor));
    }
}

NQueensJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NQueensJTests {

    int n, expected;

    @Test
    public void badN() {
        n = 0;
        expected = 0;
        assertEquals("0", expected, DPUtils.nQueens(n));
    }

    @Test
    public void oneSol() {
        n = 1;
        expected = 1;
        assertEquals("1", expected, DPUtils.nQueens(n));
    }

    @Test
    public void noSol() {
        n = 2;
        expected = 0;
        assertEquals("2", expected, DPUtils.nQueens(n));

        n = 3;
        expected = 0;
        assertEquals("3", expected, DPUtils.nQueens(n));
    }

    @Test
    public void moreSol() {
        n = 4;
        expected = 2;
        assertEquals("4", expected, DPUtils.nQueens(n));

        n = 5;
        expected = 10;
        assertEquals("5", expected, DPUtils.nQueens(n));

        n = 6;
        expected = 4;
        assertEquals("6", expected, DPUtils.nQueens(n));

        n = 7;
        expected = 40;
        assertEquals("7", expected, DPUtils.nQueens(n));

        n = 8;
        expected = 92;
        assertEquals("8", expected, DPUtils.nQueens(n));

        n = 9;
        expected = 352;
        assertEquals("9", expected, DPUtils.nQueens(n));

        n = 10;
        expected = 724;
        assertEquals("10", expected, DPUtils.nQueens(n));
    }
}

NumOfBSTsJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NumOfBSTsJTests {
    int n, expected;

    @Test
    public void catalanNumbers() {
        n = 1;
        expected = 1;
        assertEquals("1", expected, DPUtils.numOfBSTs(n));
        assertEquals("1", expected, DPUtils.numOfBSTsBottomUp(n));

        n = 2;
        expected = 2;
        assertEquals("2", expected, DPUtils.numOfBSTs(n));
        assertEquals("2", expected, DPUtils.numOfBSTsBottomUp(n));

        n = 3;
        expected = 5;
        assertEquals("3", expected, DPUtils.numOfBSTs(n));
        assertEquals("3", expected, DPUtils.numOfBSTsBottomUp(n));

        n = 4;
        expected = 14;
        assertEquals("4", expected, DPUtils.numOfBSTs(n));
        assertEquals("4", expected, DPUtils.numOfBSTsBottomUp(n));

        n = 7;
        expected = 429;
        assertEquals("7", expected, DPUtils.numOfBSTs(n));
        assertEquals("7", expected, DPUtils.numOfBSTsBottomUp(n));
    }
}

Pair.java

package com.blogspot.groglogs.structures;

import java.util.Objects;

/**
 * Defines a Pair of objects.
 * @param <T> type of the first object.
 * @param <E> type of the second object.
 */
public class Pair<T, E> {

    private T first;
    private E second;

    public Pair(T first, E second){
        this.first = first;
        this.second = second;
    }

    public T getFirst(){
        return this.first;
    }

    public E getSecond(){
        return this.second;
    }

    public void setFirst(T first){
        this.first = first;
    }

    public void setSecond(E second){
        this.second = second;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();

        if(this.first == null){
            sb.append("null,");
        }
        else{
            sb.append(this.first + ", ");
        }

        if(this.second == null){
            sb.append("null");
        }
        else{
            sb.append(this.second);
        }

        return sb.toString();
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.first, this.second);
    }

    @Override
    public boolean equals(Object o) {
        if(this == o){
            return true;
        }

        if(!(o instanceof Pair)){
            return false;
        }

        //the other pair could be typed differently, we accept it since the equals later will factor these types in
        Pair<?,?> other = (Pair<?,?>)o;

        //Objects.equals logic is: this.first == null ? other.first == null : this.first.equals(other.first)
        //which guarantees null safety AND factors in the typechecking by using the relevant equals logic of our field types
        return Objects.equals(this.first, other.first) && Objects.equals(this.second, other.second);
    }
}

ReconstructSentenceJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertEquals;

public class ReconstructSentenceJTests {

    Set<String> words;
    String text, expected;

    @Test
    public void nullEmpty() {
        text = null;
        words = null;
        expected = "";
        assertEquals("null", expected, DPUtils.reconstructSentence(words, text));

        text = "lol";
        words = new HashSet<>();
        expected = "";
        assertEquals("empty words", expected, DPUtils.reconstructSentence(words, text));

        text = "";
        words = new HashSet<>();
        words.add("lol");
        expected = "";
        assertEquals("empty text", expected, DPUtils.reconstructSentence(words, text));
    }

    @Test
    public void oneWord() {
        text = "asd";
        words = new HashSet<>();
        words.add("asd");
        expected = "asd";
        assertEquals("one word matches", expected, DPUtils.reconstructSentence(words, text));

        text = "asdasd";
        words = new HashSet<>();
        words.add("asd");
        expected = "asd asd";
        assertEquals("one word matches multiple times", expected, DPUtils.reconstructSentence(words, text));

        text = "asd";
        words = new HashSet<>();
        words.add("lol");
        expected = "";
        assertEquals("one word not matches", expected, DPUtils.reconstructSentence(words, text));

        text = "asdlol";
        words = new HashSet<>();
        words.add("lol");
        expected = "";
        assertEquals("one word not matches all text", expected, DPUtils.reconstructSentence(words, text));
    }

    @Test
    public void twoWords() {
        text = "asd";
        words = new HashSet<>();
        words.add("asd");
        words.add("lol");
        expected = "asd";
        assertEquals("two words one match", expected, DPUtils.reconstructSentence(words, text));

        text = "asdlol";
        words = new HashSet<>();
        words.add("asd");
        words.add("lol");
        expected = "asd lol";
        assertEquals("two words two matches", expected, DPUtils.reconstructSentence(words, text));

        text = "asdlolasd";
        words = new HashSet<>();
        words.add("asd");
        words.add("lol");
        expected = "asd lol asd";
        assertEquals("two words three matches", expected, DPUtils.reconstructSentence(words, text));

        text = "asdandlol";
        words = new HashSet<>();
        words.add("asd");
        words.add("lol");
        expected = "";
        assertEquals("two words no match all text", expected, DPUtils.reconstructSentence(words, text));
    }

    @Test
    public void substrings() {
        text = "asder";
        words = new HashSet<>();
        words.add("asd");
        words.add("asder");
        expected = "asder";
        assertEquals("words are prefix", expected, DPUtils.reconstructSentence(words, text));

        text = "asderasder";
        words = new HashSet<>();
        words.add("asd");
        words.add("asder");
        expected = "asder asder";
        assertEquals("double words are prefix", expected, DPUtils.reconstructSentence(words, text));

        text = "asder";
        words = new HashSet<>();
        words.add("a");
        words.add("sder");
        words.add("sd");
        words.add("er");
        expected = "a sd er";
        assertEquals("words are suffix", expected, DPUtils.reconstructSentence(words, text));

        text = "asderasder";
        words = new HashSet<>();
        words.add("a");
        words.add("sder");
        words.add("sd");
        words.add("er");
        expected = "a sd er a sd er";
        assertEquals("double words are suffix", expected, DPUtils.reconstructSentence(words, text));

        text = "asder";
        words = new HashSet<>();
        words.add("a");
        words.add("sde");
        words.add("r");
        expected = "a sde r";
        assertEquals("words are infix", expected, DPUtils.reconstructSentence(words, text));

        text = "asderasder";
        words = new HashSet<>();
        words.add("a");
        words.add("sde");
        words.add("r");
        expected = "a sde r a sde r";
        assertEquals("double words are infix", expected, DPUtils.reconstructSentence(words, text));
    }

    @Test
    public void sample(){
        text = "thequickbrownfox";
        words = new HashSet<>();
        words.add("quick");
        words.add("brown");
        words.add("the");
        words.add("fox");
        expected = "the quick brown fox";
        assertEquals("thequickbrownfox", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathandbeyond";
        words = new HashSet<>();
        words.add("bed");
        words.add("bath");
        words.add("bedbath");
        words.add("and");
        words.add("beyond");
        expected = "bed bath and beyond";
        assertEquals("bedbathandbeyond", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathandbeyond";
        words = new HashSet<>();
        words.add("bedbath");
        words.add("bath");
        words.add("beyond");
        words.add("and");
        words.add("bed");
        expected = "bed bath and beyond";
        assertEquals("bedbathandbeyond", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathbedbath";
        words = new HashSet<>();
        words.add("bedbath");
        words.add("bath");
        words.add("beyond");
        words.add("and");
        words.add("bed");
        expected = "bed bath bed bath";
        assertEquals("bedbathbedbath", expected, DPUtils.reconstructSentence(words, text));

        text = "bedban";
        words = new HashSet<>();
        words.add("bedbath");
        words.add("bath");
        words.add("beyond");
        words.add("and");
        words.add("bed");
        words.add("ban");
        expected = "bed ban";
        assertEquals("bedban", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathban";
        words = new HashSet<>();
        words.add("bedbath");
        words.add("bath");
        words.add("beyond");
        words.add("and");
        words.add("bed");
        words.add("ban");
        expected = "bed bath ban";
        assertEquals("bedbathban", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbandbath";
        words = new HashSet<>();
        words.add("bedbath");
        words.add("bath");
        words.add("beyond");
        words.add("and");
        words.add("bed");
        words.add("ban");
        words.add("band");
        expected = "bed band bath";
        assertEquals("bedbandbath", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathband";
        words = new HashSet<>();
        words.add("bed");
        words.add("bedbath");
        words.add("bedbathband");
        words.add("bath");
        words.add("band");
        words.add("beyond");
        words.add("and");
        words.add("ban");
        expected = "bed bath band";
        assertEquals("bedbathband", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathbanband";
        words = new HashSet<>();
        words.add("ban");
        words.add("bed");
        words.add("bedbath");
        words.add("bedbathband");
        words.add("bath");
        words.add("band");
        words.add("beyond");
        words.add("and");
        expected = "bed bath ban band";
        assertEquals("bedbathbanband", expected, DPUtils.reconstructSentence(words, text));

        text = "bedbathbanbandbanner";
        words = new HashSet<>();
        words.add("ban");
        words.add("banner");
        words.add("bed");
        words.add("bedbath");
        words.add("bedbathband");
        words.add("bedbathbanner");
        words.add("bath");
        words.add("band");
        words.add("beyond");
        words.add("and");
        expected = "bed bath ban band banner";
        assertEquals("bedbathbanbandbanner", expected, DPUtils.reconstructSentence(words, text));

        text = "catsandog";
        words = new HashSet<>();
        words.add("cats");
        words.add("dog");
        words.add("sand");
        words.add("and");
        words.add("cat");
        expected = "";
        assertEquals("catsandog", expected, DPUtils.reconstructSentence(words, text));
    }
}

RegexMatchJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class RegexMatchJTests {
    String text, pattern;

    @Test
    public void nullEmpty() {
        text = null;
        pattern = null;
        assertFalse("null", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = "";
        assertFalse("empty pattern", DPUtils.regexMatch(text, pattern));

        text = "";
        pattern = "";
        assertTrue("both empty", DPUtils.regexMatch(text, pattern));

        text = "";
        pattern = "asd";
        assertFalse("pattern not empty and no match", DPUtils.regexMatch(text, pattern));

        text = "";
        pattern = ".*";
        assertTrue("pattern not empty and match", DPUtils.regexMatch(text, pattern));

        text = "";
        pattern = "a*";
        assertTrue("pattern not empty and match", DPUtils.regexMatch(text, pattern));
    }

    @Test
    public void noMatch() {
        text = "asd";
        pattern = "lol";
        assertFalse("asd,lol", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = "a*sdd";
        assertFalse("asd,a*sdd", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = "..l";
        assertFalse("asd,..l", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = ".*l";
        assertFalse("asd,.*l", DPUtils.regexMatch(text, pattern));

        text = "abbbbb";
        pattern = "ab*b*b*b*b*c";
        assertFalse("abbbbb,ab*b*b*b*b*c", DPUtils.regexMatch(text, pattern));

        text = "abbbbb";
        pattern = "ab*.*b*.*b*c";
        assertFalse("abbbbb,ab*.*b*.*b*c", DPUtils.regexMatch(text, pattern));
    }

    @Test
    public void match() {
        text = "asd";
        pattern = "asd";
        assertTrue("asd,asd", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = "a*sd";
        assertTrue("asd,a*sd", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = "..d";
        assertTrue("asd,..d", DPUtils.regexMatch(text, pattern));

        text = "asd";
        pattern = ".*d";
        assertTrue("asd,.*d", DPUtils.regexMatch(text, pattern));

        text = "abbbbb";
        pattern = "ab*.*b*.*b*b";
        assertTrue("abbbbb,ab*.*b*.*b*b", DPUtils.regexMatch(text, pattern));
    }
}

Result.java

package com.blogspot.groglogs.knapsack.structures;

import java.util.ArrayList;
import java.util.List;

public class Result{
    public List<String> items;
    public List<Item> itemsList;
    public int weight, value;

    public Result(){
        this.items = new ArrayList<>();
        this.itemsList = new ArrayList<>();
        this.weight = 0;
        this.value = 0;
    }

    public Result(List<Item> itemsList, int weight, int value){
        this.items = new ArrayList<>();
        this.itemsList = itemsList;
        this.weight = weight;
        this.value = value;
    }

    public void addResultItem(String i, int weight, int value){
        this.items.add(i);
        this.weight += weight;
        this.value += value;
    }

}

SubsetOfSumKJTests.java

package com.blogspot.groglogs.test.dp;

import com.blogspot.groglogs.dp.DPUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

public class SubsetOfSumKJTests {

    int[] numbers;
    int k;
    List<Integer> expected, out;

    @Test
    public void nullEmpty() {
        numbers = null;
        k = 10;
        out = DPUtils.subsetOfSumK(k, numbers);
        assertTrue("null", out.isEmpty());

        numbers = new int[]{};
        k = 10;
        out = DPUtils.subsetOfSumK(k, numbers);
        assertTrue("empty", out.isEmpty());
    }

    @Test
    public void badK() {
        numbers = new int[]{1,2,3};
        k = 0;
        out = DPUtils.subsetOfSumK(k, numbers);
        assertTrue("k 0", out.isEmpty());
    }

    @Test
    public void targetNotReachable() {
        numbers = new int[]{1,2,3};
        k = 10;
        out = DPUtils.subsetOfSumK(k, numbers);
        assertTrue("1,2,3 k 0", out.isEmpty());
    }

    @Test
    public void targetIsElement() {
        numbers = new int[]{1,2,3,10};
        k = 10;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(10);
        assertEquals("target is element", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }

        numbers = new int[]{10};
        k = 10;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(10);
        assertEquals("target is element", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void targetReachable() {
        numbers = new int[]{1,2,3,1,2,3};
        k = 4;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(1);
        assertEquals("1,2,3,1,2,3 k 4", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }

        numbers = new int[]{2,2};
        k = 4;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(2);
        expected.add(2);
        assertEquals("2,2 k 4", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }

        numbers = new int[]{1,1,1,1,1,1};
        k = 4;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(1);
        expected.add(1);
        expected.add(1);
        assertEquals("1,1,1,1,1,1 k 4", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }

        numbers = new int[]{1,2,3};
        k = 6;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(1);
        expected.add(2);
        expected.add(3);
        assertEquals("1,2,3 k 6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }

        numbers = new int[]{3,2,1};
        k = 6;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(3);
        expected.add(2);
        expected.add(1);
        assertEquals("3,2,1 k 6", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }
    }

    @Test
    public void sample() {
        numbers = new int[]{12, 1, 61, 5, 9, 2};
        k = 24;
        out = DPUtils.subsetOfSumK(k, numbers);
        expected = new ArrayList<>();
        expected.add(12);
        expected.add(1);
        expected.add(9);
        expected.add(2);
        assertEquals("12, 1, 61, 5, 9, 2 k 24", expected.size(), out.size());
        for(int i = 0; i < expected.size(); i++){
            assertEquals("value is correct", expected.get(i), out.get(i));
        }
    }
}

Full description at:

• https://groglogs.blogspot.com/2021/07/java-longest-increasing-subsequence.html
• https://groglogs.blogspot.com/2021/07/java-simple-regex-matcher.html
• https://groglogs.blogspot.com/2021/07/java-n-queens.html
• https://groglogs.blogspot.com/2021/07/java-subset-of-sum-k.html
• https://groglogs.blogspot.com/2021/07/java-reconstruct-sentence-from-text.html
• https://groglogs.blogspot.com/2021/07/java-longest-wiggle-subsequence.html
• https://groglogs.blogspot.com/2021/07/java-catalan-numbers-number-of-unique.html
• https://groglogs.blogspot.com/2021/06/java-longest-palindromic-subsequence.html
• https://groglogs.blogspot.com/2021/06/java-longest-common-subsequence.html
• https://groglogs.blogspot.com/2021/06/java-minimum-cost-of-painting-houses.html
• https://groglogs.blogspot.com/2021/06/java-maximise-profit-to-cut-rod.html
• http://groglogs.blogspot.ch/2018/03/java-01-knapsack-problem-with-dynamic.html
• http://groglogs.blogspot.ch/2018/01/java-unbounded-knapsack-algorithm.html
• http://groglogs.blogspot.ch/2017/03/java-01-knapsack-problem-on-log-n.html