C++ 算法系列之动态规划_c++ 动态规划算法

动态规划，是为了避免递归中出现重复计算的一种策略。核心思想是自底向上的解决问题。因此解决这类问题的关键是，从n=1开始解决，递推到n=N，求得最终值
基本操作分为三步
1. 寻找最优子结构
2. 列出递归方程，自底向上的对每个新产生的子问题仅解一次并将解保存在一个表格，需要时在表中查找.
3. 根据计算出的最优解的值构造相应的最优解

example 1

有一个高度为10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，求一共有多少种走法。

1. 寻找优子结构
   子结构就是子问题，对于这个问题，可以这样思考，我已经解决了问题的倒数第二步，最后一步该怎么办。
   该题要求走10级，10级怎么走呢，我可以在第8级的时候跨2级到第10级，也可以在第9级的时候跨一级上第10级。因此10级的总走法就是8级和9级之和。 OK, 子问题就出来了，8级的走法和9级的走法。最优的8级走法和最优的9级走法就是最优子结构
2. 列出递推式
   如第一条所述，列出公式
   F(n) = F(n-1)+F(n-2)
   n=1的时候，F(1) = 1
   n=2的时候，F(2) = 2(两步一级和一步两级)
   普通递归，求F(10)会分别求F(9)和F(8), 求F(9)的时候会求F(8)和F(7)。因此F(10) 和F(9)都求了F(8)。为了省掉多余的这一步，我们可以弄出一个数组a[10]保存我们求过的所有值，这样再求的时候直接取值就好了。这也是一种办法，但是这会需要我们弄出一个数组。按照动态规划自底向上的思路，我们只需要两个值，就可以求得结果（见代码）
3. 输出结果就可以了。

int compute(int n)
{
    if(n<1)return 0;
    if(n==1)return 1;
    if(n==2)return 2;
    int a = 1;
    int b = 2;
    int temp = 0;
    for(int i = 3;i<=n;i++)
    {
        temp = a+b;
        a= b ;
        b= temp;
    }
    return temp ;

}
int main()
{
    cout << compute(10) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

example 2

假设有5台机床，每台机床需要不同的工人来进行操作，且每台机床能操作的零件数目不一样。工人总数目为10。要是机床操作的零件总数最大，需要如何安排工作。
每台机床切出的零件数和工人数为：第一台机床：50（3）， 第二台机床：100（4），第三台机床250（5），第4台机床300（5）， 第五台机床190（4）

首先1台机床的时候，我们该怎么解决，根据工人数目，能够得到最大零件数。
2台机床的时候，那么我可以选择抽部分工人去做第一台机床，剩下操作第二台机床，也可以选择第二台机床不开工，比较两种选择的最大值，就是解。
依此类推。
假设P[i]代表第 i台机床需要的工人数量， G[i]代表第i台机床切出的数量。
F(i,j)代表i台机床 j个操作工人能切出的最大零件数。
F(i,j) = max(F(i-1,j),F(i-1,j - p[i-1])+G[n-1])(其中必须j>=p[i-1], 否则F(i,j) = F(i-1,j))
.

int getMost(int m, int n, vector<int> &g, vector<int> &p)
{
    int *s = new int[(m+1)*(n+1)], i, j;//i代表机床数，j代表工人数
    for (j = 1; j<=n; j++)
    {
        s[j] = 0;
    }
    for (i = 0; i <= m; i++)
    {
        s[i*(n + 1)] = 0;
    }
    for (i = 1; i<=m; i++)
    {
        for (j = 1; j <=n; j++)
        {
            if (j<p.at(i-1))
            {
                s[i*(n+1) + j] = s[(i - 1)*(n + 1) + j];

            }
            else
            {
                s[i*(n + 1) + j] = max(s[(i - 1)*(n + 1) + j], s[(i - 1)*(n + 1) + j - p.at(i-1)] + g[i-1]);
            }
        }
    }
    return s[(m+1)*(n+1) - 1];
}
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

example 3

最长公共子序列问题
同样属于动态规划类型。解题思路也一致。
寻找最优子结构，假设X(i), Y(j)(i, j 代表X,Y的字符串长度)的最长公共串为Z(i,j).
如果X[i]==Y[j], Z(i,j) = Z(i-1,j-1)+1
否则Z(i,j) = max(Z(i-1,j),Z(i,j-1))
确定边界条件,
z(i,j) = 0 (i==0 或者j==0)
解这个方程就可以了。

void printLcs(int *c, string a, string b, int i, int j, int n)// 这个函数用于输出结果,核心思想就是递归，先根据a,b在具体位置上是否有一致字符，一致则i-1,j-1，继续寻找子问题的解，否则根据c的值的大小，缩小问题的规模
{
    if (i == 0 || j == 0)
    {
        return;
    }
    if (a.at(i-1) == b.at(j-1))
    {
        printLcs(c, a, b, i - 1, j - 1, n);
        cout << " " << a.at(i-1);
    }
    else if (c[(i - 1)*(n + 1) + j - 1] >= c[i*(n + 1) + j - 1])
    {
        printLcs(c, a, b, i - 1, j, n);
    }
    else {
        printLcs(c, a, b, i, j - 1, n);
    }
}
void lcsLength(string s1, string s2, int m, int n)
{
    int *c = new int[(m+1)*(n+1)],i,j;
    for (i = 1; i <= m; i++)
    {
        c[i*(n+1)] = 0;
    }
    for (j = 0; j <= n; j++)
    {
        c[j] = 0;
    }
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (s1.at(i - 1) == s2.at(j - 1))
            {
                c[i*(n+1)+j] = c[(i - 1)*(n+1)+j-1]+1;
            }
            else if(c[(i-1)*(n+1)+j]>=c[i*(n+1)+j-1])
            {
                c[i*(n + 1) + j] = c[(i - 1)*(n + 1) + j];
            }
            else
            {
                c[i*(n + 1) + j] = c[i*(n + 1) + j - 1];
            }
        }
    }
    printLcs(c, s1, s2, m,n,n);

}
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

example 4

带权有向图中任意两点最短路径问题
G(V,E)求Vi到Vj的最短距离
这是个富有创造性的动态规划算法。
我们上面提到的动态规划，基本都可以直接填表就可以了。
这里只有点和边，没有表可以填。
为了有表可以填写，我们引入了点Vk .
D[i,j]表示i到j的最短路径.
我们假定Vi到Vj的最短路径经过点Vk,。
那么如果 D[i,j] > D[i,k]+D[k,j],则D[i,j]=D[i,k]+D[k,j].
因此我们对每个点都当成k,不断更新我们的D[i,j]。最终获得Vi到Vj的最短路径。
为了记录最短路径，我们引入了另一个数组P[i,j], P[i j]可以被看成一个邻接矩阵。P[i,j] 记录顶点到(Vi,Vj)的最短路径中Vj的前驱节点。
比如Vi经过Vk到Vj, 则P[i,j] = P[k,j]
这个算法是个经典算法，即弗洛伊德算法。算法复杂度N的三次方

pair<double *, double *> floydwarshall(double *w, int n)//w为带权矩阵，n为图上的节点数目，w[i,j]即为点i到点j的边的长度，如果点i和点j之间没有边，则w[i,j]为1000。w[i,i]=0
{
    double * d = new double[n*n];
    int i,j, *p = new int[n*n];//p为邻接点矩阵
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==j || w[i*n+j]==1000)
            {
                p[i*n+j]=-1;//两个点 之间没有路径记作-1
            }else
            {
                p[i*n+j]=i;
            }
        }
    }
    memcpy(d,w,n*n*sizeof(double));
    for(k=0;k<n;k++)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(d[i*n+j] > d[i*n+k]+d[k*n+j])
                {
                    d[i*n+j]=d[i*n+k]+d[k*n+j];
                    p[i*n+j]=p[k*n+j];
                }
            }
        }
    }
    return make_pair(d,p);
}
void printAllPairsShortestPath(int *pi, int n, int i,j)
{
    if(i==j){
        cout << i+1 << " "
        return;
    }else if(p[i*n+j]==-1)
    {
        cout << "No path from " <<< i+1 << " to " << j+1 << endl;
    }else
    {
        printAllPairsShortestPath(pi, n, i, pi[i*n+j]);
        cout << j+1 << endl;
    }
}
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