algorithms4DynamicProgramming

1package pkg4algorithms;2 3/*4 * algorithms4DynamicProgramming.java5 * -----------------------6 * DP = solve overlapping subproblems once and reuse (memoization / tabulation).7 * Two requirements: optimal substructure + overlapping subproblems.8 *9 * Covered: Fibonacci, 0/1 knapsack, LCS, coin change (min coins), LIS, edit distance.10 */11import java.util.*;12 13public class algorithms4DynamicProgramming {14 15    // Fibonacci - bottom-up, O(n) time O(1) space16    static long fib(int n) {17        if (n < 2) return n;18        long a = 0, b = 1;19        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }20        return b;21    }22 23    // 0/1 Knapsack - max value within capacity, O(n*W)24    static int knapsack(int W, int[] wt, int[] val) {25        int n = wt.length;26        int[][] dp = new int[n + 1][W + 1];27        for (int i = 1; i <= n; i++)28            for (int w = 0; w <= W; w++) {29                dp[i][w] = dp[i - 1][w];                        // skip item i30                if (wt[i - 1] <= w)                             // take item i31                    dp[i][w] = Math.max(dp[i][w], val[i - 1] + dp[i - 1][w - wt[i - 1]]);32            }33        return dp[n][W];34    }35 36    // Longest Common Subsequence, O(m*n)37    static int lcs(String a, String b) {38        int m = a.length(), n = b.length();39        int[][] dp = new int[m + 1][n + 1];40        for (int i = 1; i <= m; i++)41            for (int j = 1; j <= n; j++)42                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)43                        ? dp[i - 1][j - 1] + 144                        : Math.max(dp[i - 1][j], dp[i][j - 1]);45        return dp[m][n];46    }47 48    // Coin change - minimum number of coins for amount (DP), O(amount*coins)49    static int coinChangeMin(int amount, int[] coins) {50        int[] dp = new int[amount + 1];51        Arrays.fill(dp, amount + 1);52        dp[0] = 0;53        for (int a = 1; a <= amount; a++)54            for (int c : coins)55                if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);56        return dp[amount] > amount ? -1 : dp[amount];57    }58 59    // Longest Increasing Subsequence, O(n^2) (O(n log n) version possible)60    static int lis(int[] nums) {61        if (nums.length == 0) return 0;62        int[] dp = new int[nums.length];63        Arrays.fill(dp, 1);64        int best = 1;65        for (int i = 1; i < nums.length; i++)66            for (int j = 0; j < i; j++)67                if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); best = Math.max(best, dp[i]); }68        return best;69    }70 71    // Edit (Levenshtein) distance, O(m*n)72    static int editDistance(String a, String b) {73        int m = a.length(), n = b.length();74        int[][] dp = new int[m + 1][n + 1];75        for (int i = 0; i <= m; i++) dp[i][0] = i;76        for (int j = 0; j <= n; j++) dp[0][j] = j;77        for (int i = 1; i <= m; i++)78            for (int j = 1; j <= n; j++)79                dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)80                        ? dp[i - 1][j - 1]81                        : 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));82        return dp[m][n];83    }84 85    public static void main(String[] args) {86        System.out.println("fib(40) = " + fib(40));87        System.out.println("knapsack = " + knapsack(50, new int[]{10, 20, 30}, new int[]{60, 100, 120}));88        System.out.println("lcs(ABCBDAB, BDCAB) = " + lcs("ABCBDAB", "BDCAB"));89        System.out.println("coinChangeMin(11, {1,2,5}) = " + coinChangeMin(11, new int[]{1, 2, 5}));90        System.out.println("lis([10,9,2,5,3,7,101,18]) = " + lis(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));91        System.out.println("editDistance(horse, ros) = " + editDistance("horse", "ros"));92    }93}