2020-11-05 22:56 已编辑华润银行_总行智能科技部_软件开发工程师

关注

<span>动态规划</span>

动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

基本思想

若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

分治与动态规划

共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.
不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。

　　　　动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。

问题特征

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

步骤

描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解

注意需要需要二维数组用容器，C++动态分配二维数组太坑爹

Outline

动态规划原理
编号动态规划：最大不下降子序列
划分动态规划：矩阵链乘、凸多边形三角剖分
数轴动态规划：0-1背包
前缀动态规划：最长公共子序列
树形动态规划：最优二分搜索树

Notes

## 编号动态规划：最大不下降子序列

　　本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。

最长不下降子序列定义：从序列中选出若干个数组成一个新的序列，不改变他们的队伍的顺序，要求新的序列里xi≤xi+1≤xi+1.....举个例子{4,6,5,7,3}，最长不下降子序列就是{4,6,7}。
子问题的表示：令dp[i]表示以第i个元素结尾的前i个元素构成的最长不下降子序列的长度
优化子结构：若最长不下降子序列包括ak，则必有一个解包含a1,a2…ak-1的最长不下降子序列，dp[i]表示为前i个元素的序列的最长不下降子序列
方程： *dp[i] = max{dp[j] | 0
伪代码：

　　　　输入a[1,...,n]　　输出：最长子序列

时间复杂度：O(n^2)

## 划分动态规划

【矩阵链乘】

优化子结构：若计算A1~n的优化顺序在k处断开矩阵链, 即A1~n=A1~k × Ak+1~n，则在A1~n的优化顺序中，对应于子问题A1~k的解必须是A1-k的优化解，对应于子问题Ak+1~n的解必须是Ak+1~n的优化解
子问题重叠性：

方程：

假设：m[i, j] = 计算Ai~j的最小乘法数； A1 ... AkAk+1 .... An 是优化解(k实际上是不可预知)

伪代码：

输入：<A1, A2, ..., An>, Ai是矩阵
输出：计算A1 x A2 x ... x An的最小代价方法

Matrix-Chain-Order(p)
n=length(p)-1；
FOR i=1 TO n DO
    m[i, i]=0;
FOR l=2 TO n DO /* 计算地l对角线*/
    FOR i=1 TO n-l+1 DO
        j=i+l-1;
        m[i, j]= ∞;
        FOR k←i To j←1 DO /* 计算m[i,j] */
             q=m[i, k]+m[k+1, j]+ pi-1pkpj
             IF q<m[i, j] THEN                  m[i,j]=q; s[i,j]=k;
Return m and s.

Print-Optimal-Parens(s, i, j) //构建最优解，输出A1-n的优化计算顺序
 IF j=i
 THEN Print “A”i;
 ELSE Print “(”
     Print-Optimal-Parens(s, i, s[i, j])
     Print-Optimal-Parens(s, s[i, j]+1, j)
     Print “)”

算法复杂度
- 计算代价的时间：三层循环 O(n3)
- 构建最优解的时间： O(n)
- 总时间复杂度：O(n3)
空间复杂度
- 使用数组m和s
- 需要空间O(n3)

【三角剖分】

优化子结构：将多边形P划分为不相交三角形的弦的集合
优化问题:

方程：设t[i,j] = <vi-1,vi,.....,vj>的优化三角剖分代价

## 数轴动态规划：0-1背包

问题描述：给定n种物品和一个背包，物品i的重量是wi，价值vi，背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？对于每种物品总能选择完全装入或不装入，一个物品最多装入一次。
等价整数规划问题：

Naive的方法：每个物品只有两种选择：不装或装，n个物品共2n个装取方案，每个装取方案的计算代价为n，总计算代价为O(n2n)
问题的划分：

定义代价矩阵m与方程：
- *定义m(i, j)* :背包容量为j，可选物品为xi,xi+1…xn时，问题的最优解代价时m[i,j]
  - m(n, j) = 0, 0 ≤ *j
  - m(n, j) = vn, j ≥**wn
  - m(i, j) = m(i+1, j), 　　 0≤ j< wi
  - m(i, j) = max{m(i+1, j), m(i+1, j-wi)+vi}, j ≥ wi
优化子结构和自底向上的代价

伪代码

输入：C>0, wi>0, vi>0, 1≤ i≤n
输出：(x1, x2, …, xn), xi∈{0, 1}, 满足 ∑1≤i≤nwi xi ≤C, ∑1≤i≤nvi xi 最大

For j=0 To min(wn-1, C) Do
      m[n, j] = 0;
For j=wn To C Do
      m[n, j] = vn;
For i=n-1 To 2 Do
    For j=0 To min(wi -1, C)  Do
      m[i, j] = m[i+1, j];
    For j=wi  To C   Do
      m[i, j]=max{m[i+1, j], m[i+1, j-wi]+vi};
If  C<w1  Then  m[1, C]=m[2, C];
      Else  m[1, C]=max{m[2, C], m[2, C-w1]+v1};

m(1, C)是最优解代价值，相应解计算如下: //构造优化解
    If m(1, C) = m(2, C)
    Then x1 = 0;
    Else x1 = 1;
如果x1=0, 由m(2, C)继续构造最优解;
如果x1=1, 由m(2, C-w1)继续构造最优解.

时间复杂度：
- 计算代价的时间为O(Cn)
- 构造最优解的时间:O(Cn)
- 总时间复杂度为:O(Cn)
空间复杂度：
- 使用数组m，需要空间O(Cn)

## 前缀动态规划：最长公共子序列（LCS）

题目来源及解析：https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a

问题描述：Z是序列X与Y的公共子序列如果Z是X的子序列也是Y的子序列。
Naive方法：
- 枚举X的每个子序列Z
- 检查Z是否为Y的子序列
- T(n)=O(n2m)
优化子结构：
- 设X=(x1, ..., xm)、Y=(y1, ..., yn)是两个序列， LCSXY=(z1, ..., zk)是X与Y的LCS，我们有：
  - 如果xm=yn, 则zk=xm=yn, LCSXY = LCSXm-1Yn-1 + , LCSXm-1Yn-1是Xm-1和Yn-1的LCS.
  - 如果xm≠yn，且zk≠xm，则LCSXY是Xm-1和Y的LCS，即 LCSXY = LCSXm-1Y
  - 如果xm≠yn,且zk≠yn,则LCSXY是X与Yn-1的LCS，即 LCSXY = LCSXYn-1

子问题重叠性

方程：

自底向上计算：

伪代码

输入：X = (x1,x2,...,xm)，Y = (y1,y2,...yn)
输出：Z = X与Y的最长公共子序列

C[0:m,0:n]: C[i,j]是Xi与Yj的LCS的长度   B[1:m,1:n]:
B[i,j]是指针，指向计算C[i,j]时所选择的子问题的优化解所对应的C表的表项

LCS-length(X, Y)
m←length(X)；n←length(Y)；
For i←0 To m Do C[i,0]←0;
For j←0 To n Do C[0,j]←0;
For i←1 To m Do
  For j←1 To n Do
    If xi = yj
    Then C[i,j]←C[i-1,j-1]+1；B[i,j]←“↖”;
      Else If C[i-1,j]≥C[i,j-1] Then
              C[i,j]←C[i-1,j]; B[i,j]←“↑”;
           Else C[i,j]←C[i,j-1]; B[i,j]←“←”;
Return C and B.

Print-LCS(B, X, i, j)
IF i=0 or j=0 THEN Return;
IF B[i, j]=“↖”
THEN Print-LCS(B, X, i-1, j-1);
    Print xi;
ELSE If B[i, j]=“↑”
    THEN Print-LCS(B, X, i-1, j);
    ELSE Print-LCS(B, X, i, j-1).

Print-LCS(B, X, length(X), length(Y))
      可打印出X与Y的LCS。

时间复杂度
- 计算代价的时间：O(mn)
- 构造最优解的时间：O(m+n)
- 总时间复杂度为： O(mn)
空间复杂度
- 使用数组C和B，需要空间O(mn)

典型问题

01背包问题

背包九讲：http://www.cnblogs.com/jbelial/articles/2116074.html

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

int main()
{
    //int m = 120;
    //int n = 5;
    //vector<int> w = { 0, 40, 50, 70, 40, 20 };
    //vector<int> v = { 0, 10, 25, 40, 20, 10 };

    int m, n;    //m重量，n数量
    while (cin >> m >> n)
    {
        vector<int> w(n + 1, 0);
        vector<int> v(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            w[i] = tmp;
        }
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            v[i] = tmp;
        }
        vector< vector<int> > vec(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (w[i] > j)
                    vec[i][j] = vec[i - 1][j];
                else
                {
                    int tmp1 = v[i] + vec[i - 1][j - w[i]];
                    int tmp2 = vec[i - 1][j];
                    vec[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
                }
            }
        }
        double val = vec[n][m] * 0.1;
        cout << val << endl;
    }

    system("pause");
}

最长公共子序列（不连续） LCS　　Longest Common Subsequence

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

cnblogs与belong，最长公共子序列为blog（cnblogs, belong），最长公共子串为lo（cnblogs, belong）

这两个问题都是用空间换空间，创建一个二维数组来记录之前的每个状态

参考：【动态规划】最长公共子序列与最长公共子串
C++实现最长公共子序列和最长公共子串

状态转移方程：

用i，j遍历两个子串x,y，如果两个元素相等就+1 ，不等就用上一个状态最大的元素

public static int lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int c[][] = new int[len1+1][len2+1];
    for (int i = 0; i <= len1; i++) {
        for( int j = 0; j <= len2; j++) {
            if(i == 0 || j == 0) {
                c[i][j] = 0;
            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
                c[i][j] = c[i-1][j-1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
    return c[len1][len2];
}

最长公共子串（连续）

状态转移方程：

区别就是因为是连续的，如果两个元素不等，那么就要=0了而不能用之前一个状态的最大元素

public static int lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int result = 0;     //记录最长公共子串长度
    int c[][] = new int[len1+1][len2+1];
    for (int i = 0; i <= len1; i++) {
        for( int j = 0; j <= len2; j++) {
            if(i == 0 || j == 0) {
                c[i][j] = 0;
            } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
                c[i][j] = c[i-1][j-1] + 1;
                result = max(c[i][j], result);
            } else {
                c[i][j] = 0;
            }
        }
    }
    return result;
}

KMP

KMP算法

硬币找零问题

假设有几种硬币，如1 5 10 20 50 100，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。

解法：

用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值。

注意要从前往后算，从后往前算无法保存状态，需要递归，效率很低，就不是动态规划了

#include <iostream>
using namespace std;

#define MaxNum  pow(2,31) - 1

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> c(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            if (i == 1 || i == 5 || i == 10 || i == 20 || i == 50 || i == 100)
            {
                c[i] = 1;
                continue;
            }
            int curMin = MaxNum;
            if (i - 1 > 0)
                curMin = c[i - 1] < curMin ? c[i - 1] : curMin;
            if (i - 5 > 0)
                curMin = c[i - 5] < curMin ? c[i - 5] : curMin;
            if (i - 10 > 0)
                curMin = c[i - 10] < curMin ? c[i - 10] : curMin;
            if (i - 20 > 0)
                curMin = c[i - 20] < curMin ? c[i - 20] : curMin;
            if (i - 50 > 0)
                curMin = c[i - 50] < curMin ? c[i - 50] : curMin;
            if (i - 100 > 0)
                curMin = c[i - 100] < curMin ? c[i - 100] : curMin;
            c[i] = curMin + 1;
        }
        cout << c[n] << endl;
    }
    

    system("pause");
    return 0;
}

类似硬币的问题找平方个数最小

题目：
给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。

#include<iostream>  
using namespace std;

int findMin(int n)
{
    int *result = new int(n + 1);
    result[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int minNum = i;
        for (int j = 1;; j++)
        {
            if (i >= j * j)
            {
                int tmp = result[i - j*j] + 1;
                minNum = tmp < minNum ? tmp : minNum;
            }
            else
                break;
        }
        result[i] = minNum;
    }
    return result[n];
}

int main()
{
    int n;
    while (cin >> n)
        cout << findMin(n) << endl;

}

最长回文字串

参考：最长回文子串

回文字符串的子串也是回文，比如P[i,j]（表示以i开始以j结束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O（N^2)，算法复杂度也是O(N^2)。

首先定义状态方程和转移方程：

P[i,j]=0表示子串[i,j]不是回文串。P[i,j]=1表示子串[i,j]是回文串。

P[i+1][j-1]&&s.at(i)==s.at(j)

初始化是准备两个元素是回文的情况aa,bb

string findLongestPalindrome(string &s)
{
    const int length=s.size();
    int maxlength=0;
    int start;
    bool P[50][50]={false};
    for(int i=0;i<length;i++)//初始化准备
    {
        P[i][i]=true;
        if(i<length-1&&s.at(i)==s.at(i+1))
        {
            P[i][i+1]=true;
            start=i;
            maxlength=2;
        }
    }
    for(int len=3;len<length;len++)//子串长度
        for(int i=0;i<=length-len;i++)//子串起始地址
        {
            int j=i+len-1;//子串结束地址
            if(P[i+1][j-1]&&s.at(i)==s.at(j))
            {
                P[i][j]=true;
                maxlength=len;
                start=i;
            }
        }
    if(maxlength>=2)
        return s.substr(start,maxlength);
    return NULL;
}

最长递增序列

问题：设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

第一种方法，排序，然后用LCS来解决：设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。

第二种：时间复杂度O(N^2)的算法：

LIS[i]：表示数组前i个元素中（包括第i个），最长递增子序列的长度

LIS[i] = max{ LIS[i] , LIS[k]+1 }, 0 <= k < i, a[i]>a[k]

LIS数组的值表示前i个元素的最长子序列。i从第一个元素到最后一个元素遍历一遍，j从第一个元素到第i个元素遍历，如果第i个元素大于j，并且LIS[J] + 1比LIS[I]还大就更新，相当于把j加入到这个递增序列了

int LIS(int a[], int length)
{
    int *LIS = new int[length];
    for(int i = 0; i < length; ++i)
    {
        LIS[i] = 1; //初始化默认长度
        for(int j = 0; j < i; ++j) //前面最长的序列
            if(a[i] > a[j] && LIS[j]+1 > LIS[i])
                LIS[i] = LIS[j]+1;  
    }
    int max_lis = LIS[0];
    for(int i = 1; i < length; ++i)
        if(LIS[i] > max_lis)
            max_lis = LIS[i];
    return max_lis;  //取LIS的最大值
}

字符串相似度/编辑距离（edit distance）

N皇后问题

其他问题

1.某幢大楼有100层。你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候，一定会有两个结果，玻璃珠碎了或者没碎。这幢大楼有个临界楼层。低于它的楼层，往下扔玻璃珠，玻璃珠不会碎，等于或高于它的楼层，扔下玻璃珠，玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。

例如：有这样一种方式，第一次选择在60层扔，若碎了，说明临界点在60层及以下楼层，这时只有一颗珠子，剩下的只能是从第一层，一层一层往上实验，最坏的情况，要实验59次，加上之前的第一次，一共60次。若没碎，则只要从61层往上试即可，最多只要试40次，加上之前一共需41次。两种情况取最多的那种。故这种方式最坏的情况要试60次。仔细分析一下。如果不碎，我还有两颗珠子，第二颗珠子会从N+1层开始试吗？很显然不会，此时大楼还剩100-N层，问题就转化为100-N的问题了。

那该如何设计方式呢？

根据题意很容易写出状态转移方程：N层楼如果从n层投下玻璃珠，最坏的尝试次数是：clip_image002[6]

那么所有层投下的最坏尝试次数的最小值即为问题的解：clip_image002[8]。其中F(1)=1.

/*
*侯凯,2014-9-15
*功能：100楼层抛珠问题
*/
#include<iostream>
using namespace std;

int max(int a, int b)
{
    return (a > b)? a : b;
}

int dp[101];
//N<=100;
int floorThr(int N)
{
    for (int i = 2; i <= N; i++)
    {
        dp[i] = i;
        for (int j = 1; j<i; j++)
        {
            int tmp = max(j, 1 + dp[i - j]);    //j的遍历相当于把每层都试一遍
            if (tmp<dp[i])
                dp[i] = tmp;
        }
    }
    return dp[N];
}

int main()
{
    dp[0] = 0;
    dp[1] = 1;
    int dis = floorThr(100);
    cout << dis << endl;
    system("Pause");
}

输出为14，说明在合适的楼层抛玻璃珠，最差情况下只需14次可找到临界层。

答案是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。

N*N方格内的走法问题

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        vector<vector<int>> dp(n+1, vector<int>(n+1, 1));
        for (int i = 1; i <= n;i++)
        {
            for (int j = 1; j <= n;j++)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        cout << dp[n][n] << endl;
    }
}

其他问题参考：

http://www.cnblogs.com/wuyuegb2312/p/3281264.html#q1a1

http://www.cnblogs.com/luxiaoxun/archive/2012/11/15/2771605.html------------恢复内容开始------------