动态规划

整理自杭电刘春英老师PPT

基本思想

如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划基本步骤：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：

• 找出最优解的性质，并刻画其结构特征。
• 递归地定义最优值。
• 以自底向上的方式计算出最优值。
• 根据计算最优值时得到的信息，构造一个最优解。

动态规划问题的特征

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：

• 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
• 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

例题

1. (HDU 1466) 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。

思路： m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数 + r条直线本身的交点方案 =（m-r）*r+r条之间本身的交点方案数（0<=r<m）

#include <iostream>
using namespace std;

long long list[21][191]={0};

int main(){
    int i,j,r;
    for(i=0; i<21; i++){
        list[i][0] = 1;
        for(r=0;r<=i;r++){
            for(j=0;j<191;j++){
                if(list[r][j]==1) // r中满足的情况
                    list[i][(i-r)*r+j] = 1; // j代表的是r中满足的交点数
            }
        }
    }
    int n;
    while(cin >>n){
        for (i=0;i<=(n-1)*n/2;i++){
            if(list[n][i]==1){
                if(i!=0)
                    cout << " ";
                cout  << i;
            }
        }
        cout << endl;
    }
}

1. (HDU 1160) FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

关键是找到动态转移方程；

#include <iostream>
#include <algorithm>
#define Maxn 10010

using namespace std;
struct node{
    int id;
    int weight;
    int speed;
    int pre;
    int  len;
}mouse[Maxn];

bool cmp(const node &m,const node &n){
    if (m.weight != n.weight)
        return m.weight < n.weight;
    return m.speed < n.speed;
}

void print_result(int num){
    if(mouse[num].len==1)
        cout << mouse[num].id << endl;
    else{
        print_result(mouse[num].pre);
        cout << mouse[num].id << endl;
    }
}

int main(){
    int cnt = 0;
    while(cin >> mouse[cnt].weight >> mouse[cnt].speed){
        mouse[cnt].id = cnt + 1;
        mouse[cnt].len = 1;
        cnt ++;
    }
    sort(mouse,mouse + cnt,cmp);
    int i,j;
    for(i=0;i<cnt;i++)
        for(j=0;j<i;j++){
            if(mouse[i].weight>mouse[j].weight && mouse[i].speed<mouse[j].speed){
                if(mouse[i].len<mouse[j].len+1){
                    mouse[i].len = mouse[j].len+1;
                    mouse[i].pre = j;
                }
            }
        }
    
    int num=0;
    for (i=0;i<cnt;i++){
        if(mouse[num].len<mouse[i].len)
            num = i;
    }
    cout << mouse[num].len << endl;
    print_result(num);
    return 0;

}

1. (HDU 1159)
   A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=1005;
long long list[maxn][maxn]={0};
int main(){
    char s1[maxn],s2[maxn];
    while(cin >>s1 >> s2){
        int l1 = strlen(s1);
        int l2 = strlen(s2);
        int i,j;
        for(i=1;i<=l1;i++)
            for(j=1;j<=l2;j++){
                if(s1[i-1]==s2[j-1])
                    list[i][j] = list[i-1][j-1] + 1;
                else
                    list[i][j] = max(list[i-1][j],list[i][j-1]);
            }
        cout << list[l1][l2] << endl;
    }
}

动态规划

原文：https://www.cnblogs.com/curtisxiao/p/10570313.html