Something About Dynamic Programming

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
 * In this program, we will calculate the Fibonacci by dynamic programming
 * The definition of the Fibonacci: Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) (n >= 2)
 * Fibonacci(1) = 1 and Fibonacci(0) = 0
 * we can find the program is faster than the recursion's
 * T(n) = O(n) and S(n) = O(1)
 */

#include <iostream>

std::size_t FibonacciByDynamicProgramming(std::size_t n) {
    std::size_t f{0}, g{1};
    for (std::size_t i = 0; i < n; i++) {
        g = g + f;
        f = g - f;
    }
    return f;
}

int main() {
    for (std::size_t i = 0; i <= 64; i++)
        std::cout << "Fibonacci(" << i << ") = " << FibonacciByDynamicProgramming(i) << std::endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

/*
 * In this program, we will use dynamic programming to find the length
 * of the longest common subsequence in two arrays
 * T(m + n) = O(m * n) and S(m + n) = O(m * n)
 */

/*
 * Example: array1[] = {1, 2, 3, 4, 5, 6, 7}
 *          array2[] = {2, 5, 6, 7}
 * we should make a matrix(n * m) and make the element in array1 and array2 in the top and left of the matrix
 * like this case:        1 2 3 4 5 6 7
 *                      2 0 0 0 0 0 0 0
 *                      5 0 0 0 0 0 0 0
 *                      6 0 0 0 0 0 0 0
 *                      7 0 0 0 0 0 0 0
 * Then we will fill the matrix top line and leftest column
 * The measuring of the matrix[1, x] x -> [1, m]:
 * The length of the longest common subsequence in array2[0] and the array1[x - 1]
 * and in the same way, we can easy to understand the measuring of the matrix[x, 1] x -> [1, n]:
 * The length of the longest common subsequence in array1[0] and the array2[x - 1]
 * so after fill, the matrix:
 *                        1 2 3 4 5 6 7
 *                      2 0 1 1 1 1 1 1
 *                      5 0 0 0 0 0 0 0
 *                      6 0 0 0 0 0 0 0
 *                      7 0 0 0 0 0 0 0
 * the base elements are ok, so we will use dynamic programming
 * if array1[x] == array2[y],we can know that it is form the "decreasing and conquer"
 * so we should make matrix[y - 1, x - 1] = matrix[y - 2, x - 2] + 1
 * else array1[x] != array2[y],we can know that it is form the "divide and conquer"
 * so we should make matrix[y - 1, x - 1] = max(matrix[y - 2, x - 1], matrix[y - 1, x - 2]
 * After the dynamic programming, the matrix:
 *                      1 2 3 4 5 6 7
 *                    2 0 1 1 1 1 1 1
 *                    5 0 1 1 1 2 2 2
 *                    6 0 1 1 1 2 3 3
 *                    7 0 1 1 1 2 3 4
 * until to matrix[n, m] we find the length of the longest common subsequence of array1 and array2
 */

#include <iostream>
#include <array>

//The algorithm
template<typename T, std::size_t N1, std::size_t N2>
std::size_t LongestCommonSubsequenceByDynamicProgramming(const std::array<T, N1> &array1, const std::array<T, N2> &array2) {
    std::array<std::array<std::size_t, N1>, N2> matrix{};
    bool flag{false};
    for (std::size_t i = 0; i < N1; i++) {
        if (flag || array1[i] == array2[0]) {
            matrix[0][i] = 1;
            flag = true;
        } else matrix[0][i] = 0;
    }
    flag = false;
    for (std::size_t i = 0; i < N2; i++) {
        if (flag || array2[i] == array1[0]) {
            matrix[i][0] = 1;
            flag = true;
        } else matrix[i][0] = 0;
    }
    for (std::size_t i = 1; i < N2; i++)
        for (std::size_t j = 1; j < N1; j++) {
            if (array1[j] == array2[i])
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
            else
                matrix[i][j] = std::max(matrix[i - 1][j], matrix[i][j - 1]);
        }
    return matrix[N2 - 1][N1 - 1];
}

int main() {
    //text code
    std::array<int, 7> v1{1, 2, 3, 4, 5, 6, 7};
    std::array<int, 4> v2{2, 5, 6, 7};
    std::array<char, 7> c1{'p', 'r', 'o', 'g', 'r', 'a', 'm'};
    std::array<char, 9> c2{'a', 'l', 'g', 'o', 'r', 'i', 't', 'h', 'm'};
    std::cout << LongestCommonSubsequenceByDynamicProgramming(v1, v2) << std::endl;
    std::cout << LongestCommonSubsequenceByDynamicProgramming(c1, c2) << std::endl;
    return 0;
}