[ADSx] - DynamicProgrammingFun

import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

class WeightedSum {

    public static int solve(int N, int K, int numbers[]) {
        int UNDEFINED = -1;
        int matrix[][] = new int[N][K+1];
        int result = 0;
        for(int i = 0; i < N; i++){
            matrix[i][1] = numbers[i];
        }
        for (int i = 1; i < N; i++) { // for numbers[]
            for (int j = 2; j < K+1; j++) {  // for the sliding window, which to choose
                for (int k = 0; k < i; k++) { // for tabular lookup
                    if (matrix[i][j] == UNDEFINED) {
                        //if (matrix[k][j - 1] != UNDEFINED) {}
                        matrix[i][j] = matrix[k][j - 1] + numbers[i] * j;

                    } else if (matrix[i][j] != UNDEFINED) {
                        /* Meaning it is defined */
                        matrix[i][j] = Math.max(matrix[i][j], matrix[k][j - 1] + numbers[i] * j);
                    }
                }
                result = Math.max(result, matrix[i][j]);
            }

        }

        return result;
    }

    public static void main(String args[]) {
        String text = "10 3\n" +
                "1 9 2 3 6 1 3 2 1 3";
        Scanner scanner = new Scanner(text);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        scanner.nextLine(); // fire off empty

        int array[] = new int[N];
        for (int i = 0; i < N; i++) {
            array[i] = scanner.nextInt();
        }

        System.out.println(solve(N, K, array));
    }
}

class AlchniVitezi {

    static int maxZlatnici(int[] zlatnici, int N) {

        int[][] maxzlatnici = new int[N][N - 1];
        for (int i = 0; i < N; i++) {
            maxzlatnici[i][0] = zlatnici[i];
            if (N > 2) {
                if (i != (N - 1))
                    maxzlatnici[i][1] = zlatnici[i + 1];
                else
                    maxzlatnici[i][1] = zlatnici[0];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 2; j < N - 1; j++) {
                maxzlatnici[i][j] = 0;
                for (int k = 0; k < j - 1; k++) {
                    if (maxzlatnici[i][j] < zlatnici[(i + j) % N] + maxzlatnici[i][k])
                        maxzlatnici[i][j] = zlatnici[(i + j) % N] + maxzlatnici[i][k];
                }
                printMatrix(maxzlatnici);
            }
            if (i > 0) {
                if (maxzlatnici[i][N - 2] < maxzlatnici[i - 1][N - 2])
                    maxzlatnici[i][N - 2] = maxzlatnici[i - 1][N - 2];
            }

        }

        printMatrix(maxzlatnici);

        return maxzlatnici[N - 1][N - 2];
    }

    static void printMatrix(int matrix[][]) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.printf("%5d", matrix[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        String text = "6\n" +
                "10 3 2 5 7 8\n";
        //Scanner scanner = new Scanner(System.in);
        Scanner scanner = new Scanner(text);
        int N = Integer.parseInt(scanner.nextLine());
        StringTokenizer st = new StringTokenizer(scanner.nextLine());
        int zlatnici[] = new int[N];
        for (int i = 0; i < N; i++) {
            zlatnici[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(maxZlatnici(zlatnici, N));
    }

}

public class DynamicProgrammingFun {
    public static void main(String args[]) {
        MinimumCostPath minimumCostPath = new MinimumCostPath();
        int cost[][] = {{1, 2, 3},
                {4, 8, 2},
                {1, 5, 3}};
        System.out.println("minimum cost to reach (2,2) = " +
                minimumCostPath.minCost(cost, 2, 2)
        );

    }
}

class Knapsack {
    /**
     * https://www.geeksforgeeks.org/knapsack-problem/
     */

    /* A Naive recursive implementation of 0-1 Knapsack problem */
    // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSackNaive(int W, int wt[], int val[], int n) {
        // Base Case
        if (n == 0 || W == 0)
            return 0;

        // If weight of the nth item is more than Knapsack capacity W, then
        // this item cannot be included in the optimal solution
        if (wt[n - 1] > W)
            return knapSackNaive(W, wt, val, n - 1);

            // Return the maximum of two cases:
            // (1) nth item included
            // (2) not included
        else return Math.max(
                val[n - 1] + knapSackNaive(W - wt[n - 1], wt, val, n - 1),
                knapSackNaive(W, wt, val, n - 1)
        );
    }

    // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSack(int W, int wt[], int val[], int n) {
        int i, w;
        int K[][] = new int[n + 1][W + 1];

        // Build table K[][] in bottom up manner
        for (i = 0; i <= n; i++) {
            for (w = 0; w <= W; w++) {
                if (i == 0 || w == 0)
                    K[i][w] = 0;
                else if (wt[i - 1] <= w)
                    K[i][w] = Math.max(
                            val[i - 1] + K[i - 1][w - wt[i - 1]],
                            K[i - 1][w]
                    );
                else
                    K[i][w] = K[i - 1][w];
            }
        }

        return K[n][W];
    }


    // Driver program to test above function
    public static void main(String args[]) {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
        int W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}

class BinomialCoefficient {
    /**
     * https://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/
     */

    // Returns value of Binomial
    // Coefficient C(n, k)
    static int binomialCoeffSimple(int n, int k) {

        // Base Cases
        if (k == 0 || k == n)
            return 1;

        // Recur
        return binomialCoeffSimple(n - 1, k - 1) +
                binomialCoeffSimple(n - 1, k);
    }

    // Returns value of Binomial Coefficient C(n, k)
    static int binomialCoeff(int n, int k) {
        int C[][] = new int[n + 1][k + 1];
        int i, j;

        // Calculate  value of Binomial Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;

                    // Calculate value using previosly stored values
                else
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }

        return C[n][k];
    }

    /* Driver program to test above function*/
    public static void main(String args[]) {
        int n = 5, k = 2;
        System.out.println("Value of C(" + n + "," + k + ") is " + binomialCoeff(n, k));
    }
}

class UglyNumber {
    /**
     * https://www.geeksforgeeks.org/?p=753
     */

    /*This function divides a by greatest divisible
    power of b*/
    int maxDivide(int a, int b) {
        while (a % b == 0)
            a = a / b;
        return a;
    }

    /* Function to check if a number is ugly or not */
    int isUgly(int no) {
        no = maxDivide(no, 2);
        no = maxDivide(no, 3);
        no = maxDivide(no, 5);

        return (no == 1) ? 1 : 0;
    }

    /* Function to get the nth ugly number*/
    int getNthUglyNoSimple(int n) {
        int i = 1;
        int count = 1; // ugly number count

        // check for all integers until count becomes n */
        while (n > count) {
            i++;
            if (isUgly(i) == 1)
                count++;
        }
        return i;
    }

    /* Function to get the nth ugly number*/
    int getNthUglyNo(int n) {
        int ugly[] = new int[n];  // To store ugly numbers
        int i2 = 0, i3 = 0, i5 = 0;
        int next_multiple_of_2 = 2;
        int next_multiple_of_3 = 3;
        int next_multiple_of_5 = 5;
        int next_ugly_no = 1;

        ugly[0] = 1;

        for (int i = 1; i < n; i++) {
            next_ugly_no = Math.min(next_multiple_of_2,
                    Math.min(next_multiple_of_3,
                            next_multiple_of_5));

            ugly[i] = next_ugly_no;
            if (next_ugly_no == next_multiple_of_2) {
                i2 = i2 + 1;
                next_multiple_of_2 = ugly[i2] * 2;
            }
            if (next_ugly_no == next_multiple_of_3) {
                i3 = i3 + 1;
                next_multiple_of_3 = ugly[i3] * 3;
            }
            if (next_ugly_no == next_multiple_of_5) {
                i5 = i5 + 1;
                next_multiple_of_5 = ugly[i5] * 5;
            }
        } /*End of for loop (i=1; i<n; i++) */
        return next_ugly_no;
    }

    /* Driver program to test above functions */
    public static void main(String args[]) {
        UglyNumber obj = new UglyNumber();
        int no = obj.getNthUglyNo(150);
        System.out.println("150th ugly no. is " + no);
    }
}

class CoinChange {

    /**
     * https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
     * Time Complexity: O(m x n)
     * <p>
     * S - array holding the types of coins
     * m - number of types of coins
     * n - total amount of money
     * S[i] - a certain type of coin, so n - S[i] is total amount minus certain coin
     */
    static long countWays(int S[], int m, int n) {
        //Time complexity of this function: O(mn)
        //Space Complexity of this function: O(n)

        // table[i] will be storing the number of solutions
        // for value i. We need n+1 rows as the table is
        // constructed in bottom up manner using the base
        // case (n = 0)
        long[] table = new long[n + 1];

        // Initialize all table values as 0
        Arrays.fill(table, 0);   //O(n)

        // Base case (If given value is 0)
        table[0] = 1;

        // Pick all coins one by one and update the table[]
        // values after the index greater than or equal to
        // the value of the picked coin
        for (int i = 0; i < m; i++)
            for (int j = S[i]; j <= n; j++)
                table[j] += table[j - S[i]];

        return table[n];
    }

    // Driver Function to test above function
    public static void main(String args[]) {
        int arr[] = {1, 2, 3};
        int m = arr.length;
        int n = 4;
        System.out.println(countWays(arr, m, n));
    }
}

class MinimumCostPath {

    /**
     * https://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/
     */

    /* A utility function that returns minimum of 3 integers */
    private static int min(int x, int y, int z) {
        if (x < y)
            return (x < z) ? x : z;
        else
            return (y < z) ? y : z;
    }

    /* Returns cost of minimum cost path from (0,0) to (m, n) in mat[R][C]*/
    int minCostRecursive(int cost[][], int m, int n) {
        if (n < 0 || m < 0)
            return Integer.MAX_VALUE;
        else if (m == 0 && n == 0)
            return cost[m][n];
        else
            return cost[m][n] + min(minCostRecursive(cost, m - 1, n - 1),
                    minCostRecursive(cost, m - 1, n),
                    minCostRecursive(cost, m, n - 1));
    }

    /**
     * Time Complexity: O(m x n)
     */

    public int minCost(int cost[][], int m, int n) {
        int i, j;
        int tc[][] = new int[m + 1][n + 1];

        tc[0][0] = cost[0][0];

        /* Initialize first column of total cost(tc) array */
        for (i = 1; i <= m; i++)
            tc[i][0] = tc[i - 1][0] + cost[i][0];

        /* Initialize first row of tc array */
        for (j = 1; j <= n; j++)
            tc[0][j] = tc[0][j - 1] + cost[0][j];

        /* Construct rest of the tc array */
        for (i = 1; i <= m; i++)
            for (j = 1; j <= n; j++)
                tc[i][j] = min(tc[i - 1][j - 1], // diagonally
                        tc[i - 1][j], // one up
                        tc[i][j - 1]) + cost[i][j]; // one left

        return tc[m][n];
    }

}

class EDIST {

    /**
     * https://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
     */

    static int min(int x, int y, int z) {
        if (x <= y && x <= z) return x;
        if (y <= x && y <= z) return y;
        else return z;
    }

    // A Naive recursive Java program to find minimum number
    // operations to convert str1 to str2
    static int editDist(String str1, String str2, int m, int n) {
        // If first string is empty, the only option is to
        // insert all characters of second string into first
        if (m == 0) return n;

        // If second string is empty, the only option is to
        // remove all characters of first string
        if (n == 0) return m;

        // If last characters of two strings are same, nothing
        // much to do. Ignore last characters and get count for
        // remaining strings.
        if (str1.charAt(m - 1) == str2.charAt(n - 1))
            return editDist(str1, str2, m - 1, n - 1);

        // If last characters are not same, consider all three
        // operations on last character of first string, recursively
        // compute minimum cost for all three operations and take
        // minimum of three values.
        return 1 + min(editDist(str1, str2, m, n - 1),    // Insert
                editDist(str1, str2, m - 1, n),   // Remove
                editDist(str1, str2, m - 1, n - 1) // Replace
        );
    }

    /**
     * Tabulated solution of Edit Distance
     * Time Complexity: O(m x n)
     */
    static int editDistDP(String str1, String str2, int m, int n) {
        // Create a table to store results of subproblems
        int dp[][] = new int[m + 1][n + 1];

        // Fill d[][] in bottom up manner
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // If first string is empty, only option is to
                // insert all characters of second string
                if (i == 0)
                    dp[i][j] = j;  // Min. operations = j

                    // If second string is empty, only option is to
                    // remove all characters of second string
                else if (j == 0)
                    dp[i][j] = i; // Min. operations = i

                    // If last characters are same, ignore last char
                    // and recur for remaining string
                else if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];

                    // If last character are different, consider all
                    // possibilities and find minimum
                else
                    dp[i][j] = 1 + min(dp[i][j - 1],  // Insert
                            dp[i - 1][j],  // Remove
                            dp[i - 1][j - 1]); // Replace
            }
        }

        return dp[m][n];
    }

}

class LongestCommonSubsequence {
    /**
     * https://www.geeksforgeeks.org/longest-common-subsequence/
     */


    /**
     * A recursive implementation of LCS problem in java
     * Returns length of LCS for X[0..m-1], Y[0..n-1]
     * Time Complexity: O(2^n)
     */
    int lcsRecursive(char[] X, char[] Y, int m, int n) {
        if (m == 0 || n == 0) return 0;
        if (X[m - 1] == Y[n - 1]) return 1 + lcsRecursive(X, Y, m - 1, n - 1);
        else return Math.max(lcsRecursive(X, Y, m, n - 1), lcsRecursive(X, Y, m - 1, n));
    }

    /**
     * Dynamic Programming Java implementation of LCS problem
     * Returns length of LCS for X[0..m-1], Y[0..n-1]
     * Time Complexity: O(m*n)
     */
    int lcsTabulation(char[] X, char[] Y, int m, int n) {
        int L[][] = new int[m + 1][n + 1];

    /* Following steps build L[m+1][n+1] in bottom up fashion. Note
         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X[i - 1] == Y[j - 1])
                    L[i][j] = L[i - 1][j - 1] + 1;
                else
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
            }
        }
        return L[m][n];
    }


    /**
     * https://www.geeksforgeeks.org/printing-longest-common-subsequence/
     */
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    void lcsPrint(String X, String Y, int m, int n) {
        int[][] L = new int[m + 1][n + 1];

        // Following steps build L[m+1][n+1] in bottom up fashion. Note
        // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i - 1) == Y.charAt(j - 1))
                    L[i][j] = L[i - 1][j - 1] + 1;
                else
                    L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
            }
        }

        // Following code is used to print LCS
        int index = L[m][n];
        int temp = index;

        // Create a character array to store the lcsPrint string
        char[] lcs = new char[index + 1];
        lcs[index] = '\0'; // Set the terminating character

        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcsPrint[]
        int i = m, j = n;
        while (i > 0 && j > 0) {
            // If current character in X[] and Y are same, then
            // current character is part of LCS
            if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                // Put current character in result
                lcs[index - 1] = X.charAt(i - 1);

                // reduce values of i, j and index
                i--;
                j--;
                index--;
            }

            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i - 1][j] > L[i][j - 1])
                i--;
            else
                j--;
        }

        // Print the lcsPrint
        System.out.print("LCS of " + X + " and " + Y + " is ");
        for (int k = 0; k <= temp; k++)
            System.out.print(lcs[k]);
    }
}

class LongestIncreasingSubsequence {
    /**
     * https://www.geeksforgeeks.org/longest-increasing-subsequence/
     */

    static int max_ref; // stores the LIS

    /**
     * To make use of recursive calls, this function must return
     * two things:
     * 1) Length of LIS ending with element arr[n-1]. We use
     * max_ending_here for this purpose
     * 2) Overall maximum as the LIS may end with an element
     * before arr[n-1] max_ref is used this purpose.
     * The value of LIS of full array of size n is stored in
     * max_ref which is our final result
     */
    static int _lisRecursive(int arr[], int n) {

        // base case
        if (n == 1) return 1;

        // 'max_ending_here' is length of LIS ending with arr[n-1]
        int res, max_ending_here = 1;

        /**
         * Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2].
         * If arr[i-1] is smaller than arr[n-1], and
         * max ending with arr[n-1] needs to be updated, then update it
         * */
        for (int i = 1; i < n; i++) {
            res = _lisRecursive(arr, i);
            if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here)
                max_ending_here = res + 1;
        }

        // Compare max_ending_here with the overall max. And
        // update the overall max if needed
        if (max_ref < max_ending_here)
            max_ref = max_ending_here;

        // Return length of LIS ending with arr[n-1]
        return max_ending_here;
    }

    // The wrapper function for _lisRecursive()
    static int lisRecursive(int arr[], int n) {
        // The max variable holds the result
        max_ref = 1;

        // The function _lisRecursive() stores its result in max
        _lisRecursive(arr, n);

        // returns max
        return max_ref;
    }

    /**
     * lisTabulated() returns the length of the longest increasing
     * subsequence in arr[] of size n with time of O(n^2)
     */
    static int lisTabulated(int arr[], int n) {
        int lis[] = new int[n];
        int i, j, max = 0;

          /* Initialize LIS values for all indexes */
        for (i = 0; i < n; i++)
            lis[i] = 1;

           /* Compute optimized LIS values in bottom up manner */
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;

           /* Pick maximum of all LIS values */
        for (i = 0; i < n; i++)
            if (max < lis[i])
                max = lis[i];

        return max;
    }

    /**
     * Additional C++ constructPrintLIS
     * https://www.geeksforgeeks.org/construction-of-longest-increasing-subsequence-using-dynamic-programming/
     */

    public static void main(String args[]) {
        int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
        int n = arr.length;
        System.out.println("Length of lis is " + lisTabulated(arr, n) + "n");
    }

}

class Fibonacci {
    /**
     * https://www.geeksforgeeks.org/dynamic-programming-set-1/
     */

    /**
     * Simple recursive program for Fibonacci numbers
     */
    public static int fibRecursive(int n) {
        if (n <= 1)
            return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }

    final int MAX = 100;
    final int NIL = -1;

    int lookup[] = new int[MAX];

    /* Function to initialize NIL values in lookup table */
    void initialize() {
        for (int i = 0; i < MAX; i++)
            lookup[i] = NIL;
    }

    /**
     * Memoization (Top Down) = Similar to Recursion
     */

    /* function for nth Fibonacci number */
    int fibMemoization(int n) {
        if (lookup[n] == NIL) {
            if (n <= 1)
                lookup[n] = n;
            else
                lookup[n] = fibMemoization(n - 1) + fibMemoization(n - 2);
        }
        return lookup[n];
    }

    /**
     * Tabulation (Bottom Up)
     */

    int fibTabulation(int n) {
        int f[] = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
}