Initial commit

9 files changed, 237 insertions, 0 deletions

diff --git a/03_dynamic_programming/a.out b/03_dynamic_programming/a.out
new file mode 100755
index 0000000..f4fc9b1
--- /dev/null
+++ b/03_dynamic_programming/a.out
diff --git a/03_dynamic_programming/coin_combinations_i_1635.cpp b/03_dynamic_programming/coin_combinations_i_1635.cpp
new file mode 100644
index 0000000..696c1f6
--- /dev/null
+++ b/03_dynamic_programming/coin_combinations_i_1635.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <vector>
+
+static constexpr int mod = 1000000007;
+static constexpr int X = 1000001;
+
+int f(const std::vector<int>& c, std::vector<int>& a, int x) {
+        if (x < 0) return 0;
+        if (a[x] != -1) return a[x];
+        if (x == 0) return a[x] = 1;
+
+        a[x] = 0;
+        for (auto m : c)
+                a[x] = (a[x] + f(c, a, x-m)) % mod;
+        return a[x];
+}
+
+int main() {
+        int n, x;
+        std::cin >> n >> x;
+        std::vector<int> c(n), a(X, -1);
+        for (int i = 0; i < n; i++)
+                std::cin >> c[i];
+        std::cout << f(c, a, x) << "\n";
+}
diff --git a/03_dynamic_programming/coin_combinations_ii_1636.cpp b/03_dynamic_programming/coin_combinations_ii_1636.cpp
new file mode 100644
index 0000000..75642da
--- /dev/null
+++ b/03_dynamic_programming/coin_combinations_ii_1636.cpp
@@ -0,0 +1,28 @@
+#include <iostream>
+#include <map>
+#include <vector>
+
+static constexpr int mod = 1000000007;
+static constexpr int X = 1000001;
+
+int main() {
+        int n, x;
+        std::cin >> n >> x;
+        std::vector<int> c(n);
+        for (int i = 0; i < n; i++)
+                std::cin >> c[i];
+
+        std::vector<std::vector<int>> a(n, std::vector<int>(X, 0));
+        for (int i = 0; i < (int)c.size(); i++) a[i][0] = 1;
+        for (int j = c.back(); j <= x; j += c.back()) a[c.size()-1][j] = 1;
+        for (int i = c.size()-2; i >= 0; i--) {
+                for (int j = 1; j <= x; j++) {
+                        a[i][j] = a[i+1][j];
+                        if (j >= c[i]) {
+                                a[i][j] += a[i][j-c[i]];
+                                a[i][j] %= mod;
+                        }
+                }
+        }
+        std::cout << a[0][x] << "\n";
+}
diff --git a/03_dynamic_programming/counting_towers_2413.cpp b/03_dynamic_programming/counting_towers_2413.cpp
new file mode 100644
index 0000000..902956b
--- /dev/null
+++ b/03_dynamic_programming/counting_towers_2413.cpp
@@ -0,0 +1,38 @@
+#include <iostream>
+#include <vector>
+
+// Recurrence relation:
+// f(n) = sum over i from 0 to n-1 of f(i) * p(n-i) 
+// where p(n) is the number of indivisible towers of height n,
+// which is easily seen to be 3^(n-1)+1.
+// Then we can expand:
+// f(n) = sum_{i=0}^{n-1} f(i)(3^{n-i-1}+1) = g(n) + h(n)
+// where we define g(n) = sum f(i)3^{n-i-1} and h(n) = sum f(i).
+// Then it's easy to see that:
+//   g(n+1) = f(n) + 3g(n)
+//   h(n+1) = f(n) + h(n)
+// Initial values are h(1) = 1 and g(1) = 1.
+
+constexpr size_t mod{1000000007};
+constexpr size_t maxn{1000001};
+std::vector<size_t> f(maxn);
+std::vector<size_t> g(maxn);
+std::vector<size_t> h(maxn);
+
+int main() {
+        g[1] = h[1] = 1;
+        f[1] = 2;
+        for (size_t i = 2; i < maxn; i++) {
+                g[i] = (f[i-1] + 3*g[i-1]) % mod;
+                h[i] = (f[i-1] + h[i-1]) % mod;
+                f[i] = (g[i] + h[i]) % mod;
+        }
+
+        size_t t;
+        std::cin >> t;
+        for (size_t i = 0; i < t; i++) {
+                size_t n;
+                std::cin >> n;
+                std::cout << f[n] << "\n";
+        }
+}
diff --git a/03_dynamic_programming/dice_combinations_1633.cpp b/03_dynamic_programming/dice_combinations_1633.cpp
new file mode 100644
index 0000000..4e76d1d
--- /dev/null
+++ b/03_dynamic_programming/dice_combinations_1633.cpp
@@ -0,0 +1,19 @@
+#include <algorithm>
+#include <array>
+#include <iostream>
+
+// We use a funny memory optimization: we only store the last 7 values.
+
+int main() {
+        constexpr unsigned mod = 1e9+7;
+        int n;
+        std::cin >> n;
+        std::array<int, 7> v{0};
+        v[0] = 1;
+        for (int i = 1; i <= n; i++) {
+                v[i%7] = 0;
+                for (int j = std::max(0, i-6); j < i; j++)
+                        v[i%7] = (v[i%7]+v[j%7]) % mod;
+        }
+        std::cout << v[n%7] << "\n";
+}
diff --git a/03_dynamic_programming/edit_distance_1639.cpp b/03_dynamic_programming/edit_distance_1639.cpp
new file mode 100644
index 0000000..0d8c6ef
--- /dev/null
+++ b/03_dynamic_programming/edit_distance_1639.cpp
@@ -0,0 +1,22 @@
+#include <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+
+int d(const std::string& a, const std::string& b, size_t i, size_t j,
+    std::vector<std::vector<int>>& t) {
+        if (t[i][j] != -1) return t[i][j];
+        if (i == a.size()) return t[i][j] = b.size()-j;
+        if (j == b.size()) return t[i][j] = a.size()-i;
+        if (a[i] == b[j]) return t[i][j] = d(a, b, i+1, j+1, t);
+        return t[i][j] = 1+std::min(d(a, b, i+1, j+1, t),
+            std::min(d(a, b, i+1, j, t), d(a, b, i, j+1, t)));
+}
+
+int main() {
+        std::string a, b;
+        std::cin >> a >> b;
+        std::vector<std::vector<int>>
+            t(a.size()+1, std::vector<int>(b.size()+1, -1));
+        std::cout << d(a, b, 0, 0, t) << "\n";
+}
diff --git a/03_dynamic_programming/longest_common_subsequence_3403.cpp b/03_dynamic_programming/longest_common_subsequence_3403.cpp
new file mode 100644
index 0000000..ca94722
--- /dev/null
+++ b/03_dynamic_programming/longest_common_subsequence_3403.cpp
@@ -0,0 +1,44 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int f(const std::vector<int>& a, const std::vector<int>& b, size_t i, size_t j,
+    std::vector<std::vector<int>>& t) {
+        if (i == a.size() || j == b.size()) return t[i][j] = 0;
+        if (t[i][j] != -1) return t[i][j];
+        if (a[i] == b[j]) return t[i][j] = 1+f(a, b, i+1, j+1, t);
+        return t[i][j] = std::max(f(a, b, i+1, j, t), f(a, b, i, j+1, t));
+}
+
+std::vector<int> read(size_t n) {
+        std::vector<int> a(n);
+        for (size_t i = 0; i < n; i++)
+                std::cin >> a[i];
+        return a;
+}
+
+int main() {
+        std::size_t n, m;
+        std::cin >> n >> m;
+        std::vector<int> a = read(n);
+        std::vector<int> b = read(m);
+        std::vector<std::vector<int>> t(n+1, std::vector<int>(m+1, -1));
+        int x = f(a, b, 0, 0, t);
+        std::cout << x << "\n";
+
+        std::vector<int> s;
+        size_t i{0}, j{0};
+        while (x > 0) {
+                if (a[i] == b[j]) {
+                        s.push_back(a[i]);
+                        i++; j++; x--;
+                } else {
+                        if (t[i+1][j] == x) i++;
+                        else j++;
+                }
+        }
+
+        for (auto x : s)
+                std::cout << x << " ";
+        std::cout << "\n";
+}
diff --git a/03_dynamic_programming/minimizing_coins_1634.cpp b/03_dynamic_programming/minimizing_coins_1634.cpp
new file mode 100644
index 0000000..f6189da
--- /dev/null
+++ b/03_dynamic_programming/minimizing_coins_1634.cpp
@@ -0,0 +1,33 @@
+#include <algorithm>
+#include <iostream>
+#include <queue>
+#include <vector>
+
+int f(const std::vector<int>& c, int x) {
+        static constexpr int max = 999999999;
+        std::vector<int> a(x+1, max);
+        std::queue<int> q;
+        a[0] = 0;
+        q.push(0);
+        while (!q.empty()) {
+                auto i = q.front();
+                q.pop();
+                for (auto k : c) {
+                        if (i + k > x || a[i+k] <= a[i]+1) continue;
+                        if (i + k == x) return a[i] + 1;
+                        a[i+k] = a[i] + 1;
+                        q.push(i + k);
+                }
+        }
+        return -1;
+}
+
+int main() {
+        int n, x;
+        std::cin >> n >> x;
+        std::vector<int> c(n);
+        for (int i = 0; i < n; i++)
+                std::cin >> c[i];
+
+        std::cout << f(c, x) << "\n";
+}
diff --git a/03_dynamic_programming/removing_digits_1637.cpp b/03_dynamic_programming/removing_digits_1637.cpp
new file mode 100644
index 0000000..8b5b334
--- /dev/null
+++ b/03_dynamic_programming/removing_digits_1637.cpp
@@ -0,0 +1,28 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+static constexpr int inf = 1999999999;
+
+std::vector<int> digits(int n) {
+        std::vector<int> d;
+        for (int i = n; i != 0; i /= 10)
+                d.push_back(i % 10);
+        return d;
+}
+
+int f(std::vector<int>& a, int n) {
+        if (a[n] != inf) return a[n];
+        for (auto d : digits(n))
+                if (d != 0)
+                        a[n] = std::min(a[n], 1+f(a, n-d));
+        return a[n];
+}
+
+int main() {
+        int n;
+        std::cin >> n;
+        std::vector<int> a(n+1, inf);
+        a[0] = 0;
+        std::cout << f(a, n) << "\n";
+}