Algorithms : complete 01-algorithmic_toolbox 04-dynamic_programming

1 files changed, 61 insertions, 4 deletions

diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
index 2ca0339..473830f 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp
@@ -1,11 +1,68 @@
 #include <iostream>
 #include <vector>
 
-using std::vector;
+using namespace std;
 
-int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) {
-  //write your code here
-  return std::min(std::min(a.size(), b.size()), c.size());
+static inline int max(int a, int b, int c) {
+    if (a > b)
+        return (a > c ? a : c);
+    return (b > c ? b : c);
+}
+
+static inline int max(int a, int b, int c, int d, int e, int f, int g) {
+    int abc = max(a, b, c);
+    int def = max(d, e, f);
+    return max(abc, def, g);
+}
+
+int lcs3(vector<int> &a, vector<int> &b, vector<int> &c)
+{
+    vector<vector<vector<int> > > cost(a.size() + 1,
+            vector<vector<int> >(b.size() + 1,
+                vector<int>(c.size() + 1, 0)));
+
+    int max_cost;;
+    for (int k = 1; k <= c.size(); k++) {
+        for (int j = 1; j <= b.size(); j++) {
+            for (int i = 1; i <= a.size(); i++) {
+                int c1 = cost[i - 1][j - 1][k - 1];     // -1 ; -1 ; -1
+                int c2 = cost[i - 1][j - 1][k];         // -1 ; -1 ;  0
+                int c3 = cost[i - 1][j][k - 1];         // -1 ;  0 ; -1
+
+                int c4 = cost[i][j - 1][k - 1];         //  0 ; -1 ; -1
+                int c5 = cost[i - 1][j][k];             // -1 ;  0 ;  0
+                int c6 = cost[i][j - 1][k];             //  0 ; -1 ;  0
+                int c7 = cost[i][j][k - 1];             //  0 ;  0 ; -1
+
+                // (-1 ; -1 ; -1) + 1
+                int c8_match = cost[i - 1][j - 1][k - 1] + 1;
+
+                if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1]) {
+#if DEBUG
+                    cout << "match " << a[i - 1] << " at (i, j, k) = " << i << "," << j << "," << k << endl;
+#endif
+                    max_cost = max(c8_match, c2, c3, c4, c5, c6, c7);
+                } else {
+                    max_cost = max(c1, c2, c3, c4, c5, c6, c7);
+                }
+                cost[i][j][k] = max_cost;
+            }
+        }
+    }
+
+#if DEBUG
+    for (int k = 0; k <= c.size(); k++) {
+        cout << "======== k = " << k << " =========" << endl;
+        for (int j = 0; j <= b.size(); j++) {
+            for (int i = 0; i <= a.size(); i++) {
+                cout << cost[i][j][k] << " ";
+            }
+            cout << endl;
+        }
+    }
+#endif
+
+    return cost[a.size()][b.size()][c.size()];
 }
 
 int main() {