动态规划算法

几道动态规划算法题解。

斐波那契数列

1
#include <iostream>
2
using namespace std;
3
4
// 动态规划求斐波那契数列
5
int fib_dp(int n) {
6
    if(n < 0)   return -1;
7
    if(n==0 || n==1)    return n;
8
    int x = 1, y = 0, s = 0;
9
    for(int i=2; i<=n; i++) {
10
        s = x + y;
11
        y = x;
12
        x = s;
13
    }
14
    return s;
15
}
16
17
int main() {
18
    int n = 0;
19
    while(n != -1) {
20
        cin >> n;
21
        cout << "F(" << n << ") = " << fib_dp(n) << endl;
22
    }
23
    return 0;
24
}

最长公共子序列问题

1. 输出公共子序列长度

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
5
// 动态规划求最长公共子序列问题
6
int lcs(string a, string b) {
7
    int n = a.size();
8
    int m = b.size();
9
    int L[n+1][m+1];
10
    for(int i=0; i<n; i++)
11
        L[i][0] = 0;
12
    for(int j=0; j<m; j++)
13
        L[0][j] = 0;
14
    for(int i=1; i<=n; i++)
15
        for(int j=1; j<=m; j++)
16
            if(a[i] == b[j])    L[i][j] = L[i-1][j-1] + 1;
17
            else    L[i][j] = max(L[i][j-1], L[i-1][j]);
18
    return L[n][m];
19
}
20
21
int main() {
22
    string a = "xzyzzyx";
23
    string b = "zxyyzxz";
24
    cout << a << " 和 " << b << " 最长公共子序列的长度为: " << lcs(a, b) << endl;
25
26
    return 0;
27
}

2. 输出所有最长的公共子序列

1
// 待完成

矩阵链相乘问题

1
// 待完成

所有点对的最短路径

1
// 测试: 4 0 7 1 6 100 0 9 100 4 4 0 2 1 100 100 0
2
#include <iostream>
3
using namespace std;
4
5
// 动态规划求所有点对的最短路径
6
int main() {
7
    int n; // 点数
8
    cin >> n;
9
    int d[n][n]; // 距离矩阵
10
    for(int i=0; i<n; i++)
11
        for(int j=0; j<n; j++)
12
            cin >> d[i][j];
13
    
14
    for(int k=0; k<n; k++)
15
        for(int i=0; i<n; i++)
16
            for(int j=0; j<n; j++)
17
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
18
19
    cout << "最短路径矩阵: " << endl;
20
    for(int i=0; i<n; i++) {
21
        for(int j=0; j<n; j++)
22
            cout << d[i][j] << ' ';
23
        cout << endl;
24
    }
25
26
    return 0;
27
}

0-1背包问题

1
// 待完成

完全背包问题

1
// 待完成

金币兑换问题

1
// 测试: 30 4 1 5 7 11
2
3
#include <iostream>
4
#include <map>
5
using namespace std;
6
7
// 动态规划求解金币兑换问题
8
// 参数: 总钱数s, 总金币种类数n, 金币面值V
9
void goldcoin(int s, int n, int V[]) {
10
    int r[s+1]; // 各个价值下所需的金币数
11
    int w[s+1]; // 各个价值下是那种金币
12
    for(int i=0; i<=s; i++)
13
        r[i] = i;
14
    for(int i=1; i<n; i++)
15
        for(int j=V[i]; j<=s; j++) {
16
            int temp = r[j-V[i]] + 1;
17
            if(temp < r[j]) {
18
                r[j] = temp;
19
                w[j] = i;
20
            }
21
        }
22
    cout << "最少金币数: " << r[s] << endl;
23
    map<int, int> map_dp; // 各种金币的个数
24
    while(s > 0){
25
        map_dp[w[s]]++;
26
        s = s - V[w[s]];
27
    }
28
    for(int i=0; i<n; i++)
29
        cout << "面值为 " << V[i] << " 的金币需要 " << map_dp[i] << " 个" << endl;
30
}
31
int main() {
32
    int s; // 总钱数
33
    int n; // 金币种类数
34
    int V[n]; // 各个金币的面值
35
    cin >> s >> n;
36
    for(int i=0; i<n; i++)
37
        cin >> V[i];
38
    goldcoin(s, n, V);
39
40
    return 0;
41
}