算法题笔记-动态规划思想

动态规划问题以前一直以为能用分治和递归来解决,想了想还是不太一样的,动态规划的子问题的解往往依赖其他同级子问题的解,而分治子问题可以直接由子子问题的解得出,另外动态规划的一个子问题经常会被多次用到,不难想到为什么动态规划一般都需要一个二维数组来保存子问题状态。尽管如此,很多子问题思路还是不那么容易想到的,这里写下几题代码备用。

导航目录

  1. 最长公共子序列
  2. 防卫导弹
  3. 田忌赛马(tian ji racing)
  4. 计算矩阵连乘积
  5. 石子合并

最长公共子序列

描述:
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1, x2,…, xm>,则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>,使得对于所有j=1,2,…,k有:

Xij = Zj

输入:
输入共两行,每行一个由字母和数字组成的字符串,代表序列A、B。A、B的长度不超过200个字符。

输出:
一个整数,表示最长各个子序列的长度。
格式:printf("%d\n");

输入样例

programming
contest

输出样例

2

使用标准的动态规划解法,还是很简单的:

#include <iostream>
#include <deque>
#include <string.h>

using namespace std;
char a[201];
char b[201];
int l[201][201];
char c[201];
int m,n;
void readData(){
    cin.getline(c,201);
     m = strlen(c);
    for(int i=0;i<m;i++)
        a[i] = c[i];

    cin.getline(c,201);
    n = strlen(c);
    for(int j=0;j<n;j++)
        b[j] = c[j];
}

void init(){
    for(int i=0;i<=m;i++){
        l[i][0] = 0;
    }
    for(int j=0;j<=n;j++)
        l[0][j]=0;
}

int max(int x,int y){
    return x>=y?x:y;
}
void manage(){
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
    {
        if(a[i-1]==b[j-1])
            l[i][j]= l[i-1][j-1]+1;
        else{
            l[i][j]=max(l[i-1][j],l[i][j-1]);
        }
    }

}
int main()
{
    readData();
    init();
    manage();
    cout<<l[m][n]<<endl;
    return 0;
}

防卫导弹问题

描述:
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行,也可以用很快的速度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行。但有一个缺点,尽管它发射时可以达到任意高度,但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这些导弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹的高度,以及它们发射次序。现要求编一程序,求在每次测试中,该防卫导弹最多能截击的进攻导弹数量,一个导弹能被截击应满足下列两个条件之一:
a)它是该次测试中第一个被防卫导弹截击的导弹;
b)它是在上一次被截击导弹的发射后发射,且高度不大于上一次被截击导弹的高度的导弹。

输入:
多个测例。
每个测例第一行是一个整数n(n不超过100),第二行n个整数表示导弹的高度(数字的顺序即发射的顺序)。
n=0表示输入结束。

输出:
每个测例在单独的一行内输出截击导弹的最大数目。

输入样例:

5
5 6 100 6 61
0

输出样例:

2

这个问题好像也是有点简单,直接找到子问题基本就解出来了

#include <iostream>

using namespace std;

void maxD(int data[],int n){
    int* result = new int[n];
    int i,j;
    for(i = n-1;i >= 0;i--){
        int tmpMax = 0;
        for(j = i+1;j < n;j++){
            if(data[i]>=data[j]&&result[j]>tmpMax){
                tmpMax = result[j];
            }
        }
        result[i] = tmpMax + 1;
    }
    for(i = 0;i<n;i++){
        if(result[0]<result[i])
            result[0] = result[i];
    }
    cout << result[0] <<endl;
    delete(result);
}

int main()
{
    int *data;
    int i,j,n;
    for(;;){
        cin>>n;
        if(n<=0) break;
        data = new int[n];
        for(i =0 ;i<n;i++){
            cin>>data[i];
        }
        maxD(data,n);
        delete(data);
    }
    return 0;
}

田忌赛马

描述:
田忌与齐王赛马,双方各有n匹马参赛(n<=100),每场比赛赌注为1两黄金,现已知齐王与田忌的每匹马的速度,并且齐王肯定是按马的速度从快到慢出场,现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金(输用负数表示)。
Tian Ji and the king play horse racing, both sides have n horse (n is no more the 100), every game a bet of 1 gold, now known king and Tian Ji each horses speed, and the king is definitely on the horse speed from fast to slow, we want you to write a program to help Tian Ji his best result is win the number gold (lost express with the negative number).

输入:
多个测例。每个测例三行:第一行一个整数n,表示双方各有n匹马;第二行n个整数分别表示田忌的n匹马的速度;第三行n个整数分别表示齐王的n匹马的速度。
n=0表示输入结束。
A plurality of test cases.
Each test case of three lines: the first line contains an integer n, said the two sides each have n horse; second lines of N integers n Tian Ji horse speed; third lines of N integers King n horse speed.
N = 0 indicates the end of input.

输出:
每行一个整数,田忌最多能赢多少两黄金。
how many gold the tian ji win

输入样例:

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
3
20 20 10
20 20 10
0

输出样例:

1
0
0
0

想了1个小时没想出来,网上看了下别人的源码,顿时头脑清晰。将田忌和齐王的马的数组由快到慢排好序,为了赢得最大收益,当田忌的快马跑不过齐王的快马时,就要让最慢的马,来和齐王的快马跑。
因此使用二维数组result[i][j]表示:第i轮赛马,田忌先从马的数组“尾部”开始使用了j匹慢马和齐王前j匹快马比,再从“头部”开始使用了i-j匹快马和齐王i-j匹快马比,所赢得的黄金。

#include <iostream>
#include <algorithm>

using namespace std;
int max(int m, int n){
    return m > n ? m : n;
}

int trans(int m, int n){
    if (m == n) return 0;
    return m > n ? 1 : -1;
}

void getMax(int tian[], int king[], int n){
    int i, j;
    int **result = new int*[n + 1];
    for (i = 0; i < n + 1; i++)
        result[i] = new int[n + 1];

    for (i = 0; i <= n; i++)
        for (j = 0; j <= n; j++)
            result[i][j] = 0;

    for (i = 1; i <= n; i++)
        result[i][0] = result[i - 1][0] + trans(tian[i - 1], king[i - 1]);

    for (i = 1; i <= n; i++)
        for (j = 1; j <= i; j++)
            if (j == i)
                result[i][j] = result[i - 1][j - 1] + trans(tian[n - j], king[i - 1]);
            else
                result[i][j] = max(result[i - 1][j] + trans(tian[i - j - 1], king[i - 1]),
                result[i - 1][j - 1] + trans(tian[n - j], king[i - 1]));

    int max = result[n][0];
    for (i = 1; i <= n; i++)
        max = result[n][i] > max ? result[n][i] : max;
    cout << max << endl;
    for (i = 0; i < n + 1; i++)
        delete[]result[i];
    delete[]result;
}

bool complare(int a, int b)
{
    return a>b;
}

int main()
{
    int *tian, *king, n,i;
    for (;;){
        cin >> n;
        if (n == 0) break;
        tian = new int[n + 1];
        king = new int[n + 1];
        for (i = 0; i < n; i++){
            cin >> tian[i];
        }
        for (i = 0; i < n; i++){
            cin >> king[i];
        }
        sort(tian, tian + n, complare);
        sort(king, king + n, complare);
        getMax(tian, king, n);
        delete[] tian;
        delete[] king;
    }
    return 0;
}

矩阵连乘

描述:
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵,B是一个q×r的矩阵,则其乘积C=AB是一个p×r的矩阵。计算C=AB总共需要p×q×r次乘法。
现在的问题是,给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的,i=1,2,…,n-1
要求计算出这n个矩阵的连乘积A1A2…An最少需要多少次乘法。

输入:
输入数据的第一行是一个整树n(0 < n <= 10),表示矩阵的个数。
接下来的n行每行两个整数p,q( 0 < p,q < 100),分别表示一个矩阵的行数和列数。

输出:
输出一个整数:计算连乘积最少需要乘法的次数。

输入样例

10 
1 2 
2 3 
3 4 
4 5 
5 6 
6 7 
7 8 
8 9 
9 10 
10 11

输出样例

438

使用动态规划,那么子问题就是第i个矩阵到第j个矩阵最少需要乘法的次数,使用二维数组result[i][j]就表示每个子问题的解:第i个矩阵到第j个矩阵最少乘法次数,因此推导到最后,result[0][n]的值就是原问题的解:

假设五个矩阵为1 2,2 3,3 4,4 5,5 6,则动态规划二维数组result[i][j]推导的过程如下:

动态规划

假设要推导出下表的64(从0行0列开始,第1行第3列),即第1个矩阵到第3个矩阵最少乘法次数。这时有两种情况:第一种,2、3矩阵的连乘后再乘以第1矩阵,即2*(3*5)+2、3矩阵的连乘最少次数,其中2、3矩阵的连乘最少次数即上表第2行第3列的60,所以这里值为68;第二种,1、2矩阵连乘后再乘以第3矩阵,即(2*4)*5+24=64。故取两种情况最小的值64,其他位置的值以此类推即可得到:

动态规划

动态规划

#include <iostream>

using namespace std;

int max(int m, int n){return m < n ? m : n;}

int main(){
    int **result, n, i, j, k;
    cin >> n;
    int (*data)[2] = new int[n][9];
    for (i = 0; i < n; i++){
        cin >> data[i][0] >> data[i][10];
    }
    result = new int*[n];
    for (i = 0; i < n; i++){
        result[i] = new int[n];
    }

    for (i = 0; i<n; i++){
        result[i][i] = 0;
    }

    for (k = 1; k < n; k++){
        for (i=0,j = k; j <n; i++,j++){
            int maxTmp = max(data[i][0] * data[i][11]*data[j][12] + result[i + 1][j],result[i][j-1]+data[i][0]*data[j][0]*data[j][13]);
            for (int p = 1; i + p < j-1; p++){
                maxTmp = max(result[i][i + p] + result[i + p + 1][j] + data[i][0]*data[p][14]*data[j][15], maxTmp);
            }
            result[i][j] = maxTmp;
        }
    }

    cout << result[0][n-1]<< endl;
    for (i = 0; i < n; i++)
        delete []result[i];
    delete[]result;
    return 0;
}

石子合并

描述:
在一个圆形操场的四周摆放着n堆石子(n<= 100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n-1次合并,得分的总和最小;比如有4堆石子:4 4 5 9 则最佳合并方案如下:

4 4 5 9 score: 0
8 5 9 score: 8
13 9 score: 8 + 13 = 21
22 score: 8 + 13 + 22 = 43

输入:
可能有多组测试数据。 当输入n=0时结束! 第一行为石子堆数n(1<=n<=100);第二行为n堆的石子每堆的石子数,每两个数之间用一个空格分隔。

输出:
合并的最小得分,每个结果一行。

输入样例

4 4 4 5 9 0

输出样例

43

总感觉这题和上一题非常相似,最大差别就是需要考虑环形的情况,修改一下上题子问题的思想:result[i][j]表示从第i堆石子开始的以及之后j堆石子合并得到的最小得分总和。

二维数组递推结果如下表:

004.png

#include <iostream>
using namespace std;

int max(int m, int n){ return m < n ? m : n; }

int sum(int* data, int begin, int offset,int n){
    int all = 0;
    for (int i = 0; i <= offset; i++){
        all += data[(begin + i)%n];
    }
    return all;
}

int getresult(int *data, int n){
    int **result, i, j, p;
    result = new int*[n];
    for (i = 0; i < n; i++){
        result[i] = new int[n];
        result[i][0] = 0;
    }
    for (j = 1; j < n; j++){
        for (i = 0; i < n; i++){
            result[i][j] = result[i][0] + result[(i + 1) % n][j - 1];
            for (p = 1; p < j; p++){
                int a = (i + p + 1) % n;
                int b = j - p - 1;
                result[i][j] = max(result[i][p] + result[(i + p + 1) % n][j - p - 1], result[i][j]);
            }
            result[i][j] += sum(data, i, j, n);
        }
    }
    int min = result[0][n - 1];
    delete[] result[0];
    for (i = 1; i < n; i++){
        min = result[i][n - 1] < min ? result[i][n - 1] : min;
        delete[] result[i];
    }
    return min;
}

int main(){
    int *data, n, i;
    for (;;){
        cin >> n;
        if (n == 0) break;
        data = new int[n];
        for (i = 0; i < n; i++){
            cin >> data[i];
        }
        cout << getresult(data, n) << endl;
        delete[] data;
    }
    return 0;
}

标签: 动态规划, dp, 程序算法

添加新评论