动态规划的总结

Posted on   |   In   |  

动态规划的总结

动态规划的总结

4个步骤设计一个动态规划的算法

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值，通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解

钢条切割

出售长度为i英寸的钢条的价格为$p_i(i = 1, 2, 3, …, 单位为美元)$,给定一段长度为n英寸的钢条和一个价格表，求切割方案，使得销售利益最大

长度i 1 2 3 4 5 6 7 8 9 10
价格$p_i$ 1 5 8 9 10 17 17 20 24 30

考虑一段长度为n的钢条，我们可以将钢条分成(1, n-1),(2, n-2)….(n-1, 1)这几种,然后在这几种中寻找最优的方案，递归求已分割的两段的最优方案
用数学表达式描述为
$$r_n = max(p_n,\ r_1+r_{n-1},\ r_2+r_{n-2},…,\ r_{n-1} +r_1)$$

矩阵链乘法

给定一个n个矩阵的序列$< A_1, A_2, A_3, …, A_n >$,矩阵$Ai$的规模为$ p{i-1} * p_i(1 \leq i \leq n)$,求完全括号化方案，使得计算乘积所需标量乘法次数最少

最大连续子序列的和

给定数组，求数组的最大连续子序列的和

递推关系式为：
$$max\_sum[i+1] = max(max\_sum[i] + a[i+1], a[i+1])$$
我们想要的是
$$max\_sum = max(max\_sum[1], max\_sum[2],…, max\_sum[n])$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*穷举法  O(n^3) */
int MaxSubSequence(const int A[], int N){
  int ThisSum,MaxSum,i,j,k;
  MaxSum = 0;
  for(i=0;i<N;i++)           //定起点
  {
    for(j=i;j<N;j++)         //定终点
    {
      ThisSum = 0;
      for(k=i;k<=j;k++)       //循环计算出最大的
      {
        ThisSum += A[k];
      }
      if(ThisSum > MaxSum)
        MaxSum = ThisSum;
    }
  }
  return MaxSum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int MaxSubSequence(const int A[], int N){
  int ThisSum,MaxSum,i,j;
  MaxSum = 0;
  for(i=0;i<N;i++)
  {
    ThisSum = 0;
/*
 *此处只关心起点，因为若使得thisSum变小的数列元素，一定不是以i为起点的最大
 *子序列和的一部分
 */
    for(j=i;j<N;j++)   
    {
      ThisSum += A[j];
      if(ThisSum > MaxSum)
        MaxSum = ThisSum;
    }
  }
  return MaxSum;
}
1
2
3
4
5
6
7
8
9
/*此处是对动态规划的一个变种*/
int now_sum = max_sum = 0;
for(int i=0; i<N; i++) {
    now_sum += A[i];
    if (now_sum > max_sum)
        max_sum = now_sum;
    else if (now_sum < 0)   //实际上是比较sum[i+1]与a[i+1]的大小
        now_sum = 0;
}
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
/*动态规划*/
#include <cstdio>
#include <iostream>
#include <algorithm>

const int MAX_N=10000;
int max_sum[MAX_N];   //max_sum[i]表示以a[i]结尾的最大子序列的和
int start[MAX_N];     //start表示a[i]的maxSum的起点
using namespace std;

int maxSubSum(int a[], int n){
    fill(max_sum, max_sum+n, 0);
    fill(start, start+n, 1);
    max_sum[0] = a[0];
    int ret = 0;
    for (int i = 1; i < n ; i++){
        if(max_sum[i - 1] + a[i] < a[i]){
            max_sum[i] = a[i];
            start[i] = i+1;
        }else{
            max_sum[i] = max_sum[i - 1] + a[i];
            start[i] = start[i - 1];
        }
        if (max_sum[i] > ret)
            ret = max_sum[i];
    }
    return ret;
}
int main ()
{
    int arr[] = {1,2,-5,9,-4,11,-5,6,-7,8};
    int length = sizeof(arr)/sizeof(int);
    printf("maxSum is %d\n",maxSubSum(arr, length));
    for(int i = 0; i < length; i++){
        printf("The start  is %d\n", start[i]);
    }
    return 0;
}

最长递增子序列(LIS)

最长递增子序列（LIS）的问题是要找到一个给定序列的最长子序列的长度，使得子序列中的所有元素被排序的顺序增加。
例如，{10，22，9，33，21，50，41，60，80}LIS的长度是6和LIS为{10，22，33，50，60，80}。给定数列array[n];

  • 动态规划
    dp[i]表示的是以array[i]结尾的LIS，则

$$dp[i] =
\begin{cases}
max(dp[j] + 1)\ (j = 0,1, 2..,i-1) ,& \text{如果$a[j]$ > $a[i]$} \\
1, & \text{otherwise} \\
\end{cases}$$

$$dp[i] = \begin{cases} max(dp[j] + 1)\ (j = 0,1, 2..,i-1) ,& \text{如果$a[j]$ > $a[i]$} \\ 1, & \text{otherwise} \\ \end{cases}$$ 
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
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
using namespace std;

/* 最长递增子序列 LIS
 * 设数组长度不超过 30
 * DP
*/
const int SIZE = 100;
/*dp[i]表示以my_array[i]结尾的LIS的长度
 *（dp[i]表示从array[0]到array[i]构成的序列的LIS的长度（错误））
 */
int dp[SIZE];   
int lis = 1;
int LIS_DP(int my_array[], int n){
    for (int i = 0; i < n; i++){
        dp[i] = 1;
        for( int j= 0; j < i; j++){
            /*特别需要注意的是，此处为递增序列，并非非递减序列*/
            if (my_array[j] < my_array[i] && dp[j] + 1 > dp[i]){
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > lis){
            lis = dp[i];
        }
    }
    return lis;
}

void print_LIS(int my_array[], int index){
    int pos = lis;
    
    if(index < 0 || lis == 0)
        return;
    int inLIS = 0;
    if(dp[index] == lis){
        inLIS = 1;
        lis--;
    }
    
    print_LIS(my_array, --index);

    if(inLIS){
        printf("The %d of LIS is %d\n", pos, my_array[index+1]);
    }
}

int main(){
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };

    /* 输出LIS长度； sizeof 计算数组长度 */
    printf("%d\n",LIS_DP(arr,sizeof(arr)/sizeof(int)));

    /* 输出LIS */
    print_LIS(arr,sizeof(arr)/sizeof(int) - 1);
    printf("\n");
    return 0;
}
  • 还可以采用排序+LCS的方法
  • 还有一种巧妙的方法，复杂度为$O(nlog(n))$
    所有三种的方法实现 链接

    最长公共子序列(LCS)

    具体见链接