Add dynamic questions

prabhupant · prabhupant · commit b7d04e814dc2 · 2020-02-02T20:06:31.000+05:30
diff --git a/algorithms/dynamic_programming/coin_change.py b/algorithms/dynamic_programming/coin_change.py
@@ -0,0 +1,16 @@
+# Concept is almost same as 01 Knapsack Problem
+
+def min_coin(coins, total):
+    cols = total + 1
+    rows = len(coins)
+
+    t = [ [0] if col == 0 else float('inf') for col in range(cols)] for i in range(rows)]
+
+    for i in range(rows):
+        for j in range(1, cols):
+            if j < coins[i]:
+                t[i][j] = t[i-1][j]
+            else:
+                t[i][j] = min(t[i-1][j], 1 + t[i][j-coins[i])
+
+    return t[rows-1][cols-1]
diff --git a/algorithms/dynamic_programming/longest_common_subsequence.py b/algorithms/dynamic_programming/longest_common_subsequence.py
@@ -0,0 +1,18 @@
+def lcs(s1, s2):
+    cols = len(s1) + 1
+    rows = len(s2) + 1
+
+    t = [[0 for i in range(cols)] for i in range(rows)]
+
+    max_length = 0
+
+    for i in range(1, rows):
+        for j in range(1, cols):
+            if s2[i-1] == s1[j-1]:
+                t[i][j] = 1 + t[i-1][j-1]
+            else:
+                t[i][j] = max(t[i-1][j], t[i][j-1])
+
+            max_length = max(max_length, t[i][j])
+
+    return max_length
diff --git a/algorithms/dynamic_programming/longest_common_substring.py b/algorithms/dynamic_programming/longest_common_substring.py
@@ -0,0 +1,15 @@
+def lcs(s1, s2):
+    cols = len(s1) + 1
+    rows = len(s2) + 1
+
+    t = [[0 for i in range(cols)] for i in range(rows)]
+
+    max_length = 0
+
+    for i in range(1, rows):
+        for j in range(1, cols):
+            if s[i-1] == s[j-1]:
+                t[i][j] = t[i-1][j-1] + 1
+                max_length = max(max_length, t[i][j])
+
+    return max_length
