Dynamic Programming

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

int knapsack(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { dp[i][w] = dp[i-1][w]; // Don't take item i if (weights[i-1] <= w) // Take item i dp[i][w] = Math.max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]); } } return dp[n][capacity]; }

int lcs(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); return dp[m][n]; }

int minCoins(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) for (int coin : coins) if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1); return dp[amount] > amount ? -1 : dp[amount]; }

int lis(int[] arr) { int n = arr.length; int[] dp = new int[n]; Arrays.fill(dp, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1); maxLen = Math.max(maxLen, dp[i]); } return maxLen; }

int editDistance(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])); return dp[m][n]; }