算法课第七章

Posted on

动态规划

由递归获取递推表达式，再尝试转为自底向上（减少重复），最后尝试进行各种优化

定义一个数组，

二项式系数

二项式系数.png

  • 直接计算

    略

以下方法所需要的数组:

1
2
3
int dp[m+1][n+1];
for (int i=0; i<=n; ++i) dp[0][i] = 1;
for (int i=0; i<=m; i++) dp[i][i] = 1;

  • 利用公式，自底向上

    1
    2
    3
    4
    5
    6
    for (int i=1; i<=m; ++i) {
    	for (int j=i+1; j<=n; ++j) {
    		dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
    	}
    }
    printf("%d", dp[m][n]);

  • 时间复杂度优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 按行计算
    for (int i=1; i<=m; ++i) {
    	for (int j=i+1; j<=(i+n-m); ++j) { // 一行中，只需计算 n-m 个即可 [i+1, i+n-m] 
    		dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
    	}
    } 
    printf("%d", dp[m][n]);

    // 按对角线计算
    for (int i=1; i<=(n-m); ++i) { // i表示 (x, y)， i = y-x; 对角线的差值 
    	for (int j=1; j<=m; ++j) { // 行数 
    		int y = i+j;           // 每个要求元素的纵坐标 			
            dp[i][y] = dp[i-1][y-1] + dp[i][y-1];
    	}
    }
    printf("%d", dp[m][n]);

  • 存储空间优化（可以用一维数组来保存一行的值）

    1
    2
    3
    4
    5
    6
    7
    int dp1[n-m+1]; // dp1[0]代表C(n, m)中，m=n的情况 
    for (int i=0; i<=(n-m+1); ++i) dp1[i] = 1;
    	for (int i=1; i<=m; ++i) { // m行 
    		for (int j=1; j<=(n-m); ++j) // 每行计算前n-m个 
    			dp1[j] = dp1[j] + dp1[j-1];
    }
    printf("%d", dp1[n-m]);

过河问题

QQ截图20200402090210.png

这个问题和【数塔】问题非常相似，状态都具有无后效性

这里需要开一个二维数组，dp[i][0]表示第i个桥之前所有路径中的最小值

有递推式：dp[i][0] = min(dp[i-1][0] + C + S, dp[i-1][1] + C + S)

这里的C和S为前一个桥和路径的值，因为不方便使用下标，所有简写了

最长公共子序列

  • 二维数组的实现

    递推式:

    • 当a[i]!=b[j]时：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    • 当a[i]==b[j]时：dp[i][j] = d[i-1][j-1] + 1

    只能遍历所有的位置，因为求任一元素，需要其左，上，左上的元素（画图就知道了）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int findLCS(string A, int n, string B, int m) {
    	int dp[n+1][m+1];
      string LCS;
      for(int i = 0;i <= n;++i) dp[i][0] = 0;
      for(int i = 0;i <= m;++i) dp[0][i] = 0;
    		
    	for (int i=0; i<n; ++i) {
    		for (int j=0; j<m; ++j) {
    			if (A[i] == B[j]) {
            LCS += A[i];
            dp[i+1][j+1] = dp[i][j] + 1;
    	  } else
    				dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
    		}
    	}
      cout<<LCS<<"\n";
    	return dp[n][m];
    }

如何从长度得到最长公共子序列
从dp[m][n]出发，如果a[i]==b[j]，则同时减一（走对角线），否则，找 左侧 和 上面 较大的那一个。在这个过程中，把走对角线的记录下来，就是最长公共子序列。

矩阵相乘

问题：求出计算n各矩阵相乘M1M2M3…Mn所需要的最少的乘法次数

需要知道的知识：

  1. 如果M1M2分别时axb和bxc的，那么计算M1M2需要的数量乘法为axbxc次
  2. 矩阵乘法具有结合率，不具有交换律

例子：
三个矩阵M1,M2,M3，M1是10x2的，M2是2x10的，M3是10x2的，求相乘M1M2M3次数

  1. 如果按顺序，则(M1M2)M3,一共400次
  2. 如果M1(M2M3),一共80次！！