1 files changed, 115 insertions, 15 deletions
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
index 0131b53..4ce529b 100644
--- a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
+++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp
@@ -4,28 +4,128 @@
 
 using std::vector;
 
-vector<int> optimal_sequence(int n) {
-  std::vector<int> sequence;
-  while (n >= 1) {
-    sequence.push_back(n);
-    if (n % 3 == 0) {
-      n /= 3;
-    } else if (n % 2 == 0) {
-      n /= 2;
-    } else {
-      n = n - 1;
+// How to express C(n) through C(n/3), C(n/2), C(n − 1):q
+
+vector<int> optimal_sequence(int n)
+{
+    std::vector<int> sequence;
+    while (n >= 1) {
+        sequence.push_back(n);
+        if (n % 3 == 0) {
+            n /= 3;
+        } else if (n % 2 == 0) {
+            n /= 2;
+        } else {
+            n = n - 1;
+        }
     }
-  }
-  reverse(sequence.begin(), sequence.end());
-  return sequence;
+    reverse(sequence.begin(), sequence.end());
+    return sequence;
+}
+
+#define NAN std::numeric_limits<int>::max()
+
+static inline int best(int a, int b, int c)
+{
+    int r = std::numeric_limits<int>::max();
+
+    if (c != 0 && c < r)
+        r = c;
+    if (b != 0 && b < r)
+        r = b;
+    /* if (a != 0 && a < r) */
+    if (a < r)
+        r = a;
+
+    return r;
+}
+
+static inline int which(int a, int b, int c)
+{
+    int i = -1;
+    int r = std::numeric_limits<int>::max();
+
+    if (c != 0 && c < r) {
+        r = c;
+        i = 2;
+    }
+    if (b != 0 && b < r) {
+        r = b;
+        i = 1;
+    }
+    /* if (a != 0 && a < r) */
+    if (a < r)
+        i = 0;
+
+    return i;
+}
+
+vector<int> jzu(int n)
+{
+    vector<int> solution;
+
+    int N = n + 1;
+	int *add1  = new int[N];
+	int *mult2 = new int[N];
+	int *mult3 = new int[N];
+
+    add1[2] = mult2[2] = mult3[3] = 1;
+    add1[3] = 2;
+    /* std::cout << "0| " << add1[0] << " " << mult2[0] << " " << mult3[0] << std::endl; */
+    /* std::cout << "1| " << add1[1] << " " << mult2[1] << " " << mult3[1] << std::endl; */
+    /* std::cout << "2| " << add1[2] << " " << mult2[2] << " " << mult3[2] << std::endl; */
+    /* std::cout << "3| " << add1[3] << " " << mult2[3] << " " << mult3[3] << std::endl; */
+
+    int c3 = 0;
+    bool even = true;
+    for (size_t i = 4, j = 3; i < N ; i++, j++) {
+
+        add1[i] = best(add1[j], mult2[j], mult3[j]) + 1;
+
+        if (even) {
+            int k = i >> 1;
+            mult2[i] = best(add1[k], mult2[k], mult3[k]) + 1;
+        }
+
+        if (c3 == 2) {
+            int k = i / 3;
+            mult3[i] = best(add1[k], mult2[k], mult3[k]) + 1;
+            c3 = 0;
+        } else
+            c3++;
+
+        even = !even;
+        /* std::cout << i << "| " << add1[i] << " " << mult2[i] << " " << mult3[i] << std::endl; */
+    }
+
+    while (n > 1) {
+        solution.push_back(n);
+        int op = which(add1[n], mult2[n], mult3[n]);
+        if (op == 0) {
+            n--;
+        } else if (op == 1) {
+            n /= 2;
+        } else
+            n /= 3;
+    }
+    solution.push_back(1);
+
+    delete [] add1;
+    delete [] mult2;
+    delete [] mult3;
+
+    return solution;
 }
 
 int main() {
   int n;
   std::cin >> n;
-  vector<int> sequence = optimal_sequence(n);
+  /* vector<int> sequence = optimal_sequence(n); */
+  vector<int> sequence = jzu(n);
   std::cout << sequence.size() - 1 << std::endl;
-  for (size_t i = 0; i < sequence.size(); ++i) {
+  for (size_t i = sequence.size() - 1; i > 0; i--) {
     std::cout << sequence[i] << " ";
   }
+  std::cout << sequence[0] << " ";
+  std::cout << '\n';
 }