package cz.cvut.fel.alg;

/**
 * Playground for dynamic programming algorithms
 *
 * @author Petr Ryšavý, Karel Horák
 */
public class DynamicProgramming {

    public static void main(String[] args) {
        // use this method for debugging your code
        // you may also want to run our tests that are available in test packages (i.e. test directory)
        
        // Run tests
        for(int n = 0 ; n <= 10 ; n++) {
            for(int k = 0 ; k <= n ; k++) {
                System.out.printf("%4d ", binomialDP(n, k));
            }
            System.out.println();
        }
        System.out.println();

        for(int i = 0 ; i <= 10 ; i++) System.out.println(numberOfValidStringsDP(i));
    }

    /**
     * Computes Fibonacci number using recursion
     *
     * @param n
     * @return F(n)
     */
    public static long fibonacciRecursive(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
    }

    /**
     * Computes Fibonacci number using dynamic programming
     *
     * @param n
     * @return F(n)
     */
    public static long fibonacciDP(int n) {
        long[] vals = new long[Math.max(2,n+1)];
        vals[0] = 0;
        vals[1] = 1;
        for(int i = 2 ; i <= n ; i++) vals[i] = vals[i-2] + vals[i-1];
        return vals[n];
    }

    /**
     * Computes binomial coefficient using recursion
     *
     * @param n
     * @param k
     * @return n \over k
     */
    public static long binomialRecursive(int n, int k) {
        if(k < 0 || k > n) return 0;
        if(n == 0 || k == 0) return 1;
        else return binomialRecursive(n-1, k) + binomialRecursive(n-1, k-1);
    }

    /**
     * Computes binomial coefficient using dynamic programming
     *
     * @param n
     * @param k
     * @return n \over k
     */
    public static long binomialDP(int n, int k) {
        long[][] table = new long[n+1][n+1];
        for(int in = 0 ; in <= n ; in++) {
            table[in][0] = 1;
            table[in][in] = 1;
            for(int ik = 1 ; ik < in ; ik++) table[in][ik] = table[in-1][ik] + table[in-1][ik-1];
        }
        return table[n][k];
    }

    /**
     * Computes number of valid 0/1 strings of length n using recursion
     * @param n
     * @return
     */
    public static long numberOfValidStringsRecursive(int n) {
        if(n == 0) return 0;
        else return numberOfValidStringsRecursiveHelper(n, 0) + numberOfValidStringsRecursiveHelper(n, 1);
    }
    public static long numberOfValidStringsRecursiveHelper(int n, int last) {
        if(n == 1) return 1;
        else if(last == 1) return numberOfValidStringsRecursiveHelper(n-1, 0);
        else return numberOfValidStringsRecursiveHelper(n-1, 1) + numberOfValidStringsRecursiveHelper(n-1, 0);
    }

    /**
     * Computes number of valid 0/1 strings of length n using dynamic programming
     * @param n
     * @return
     */
    public static long numberOfValidStringsDP(int n) {
        if(n == 0) return 0;

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

}