《算法导论》笔记 PART 4

发布于 2020-02-25  104 次阅读


第四部分:高级设计与分析技术

第15章:动态规划

动态规划和之前的第四章的分治有些许类似,其本质是通过状态的转移来实现对问题的求解,但和分治算法将大问题分解成小问题然后合并的思想不同的是,动态规划着眼于不同状态之间的转移,通过编写不同状态之间状态转移方程,然后通过搜索或递推的方式来求解问题,

其在求解问题的时候能很有效的解决重叠子问题的重复计算问题(类似于记忆化搜索),其目的大多都在于求解有最优解的问题

15.1钢条切割问题

对于一个长度为m的钢条,给你市场上对各种长度的钢条的价格表,让你将这根钢条切成几段,从而使售价最大化。

根据前几张的知识,我们可以用分治的思想来解决这个问题.通过不断向下求解最大值的办法来解决,这种从大规模到小规模的算法叫做自顶向下法

int prize[100000]; //价格表
int cut_rod(int n)
{
    if (n == 0)
        return 0; //没有钢管可切
    int ans = -0x7FFFFFFF;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, prize[i] + cut_rod(n - i));
    }
    return ans;
}

但是这样的算法的时间复杂度高达O(2^n),一般计算机只能求解m<100以内的问题,显然是不合格的。通过观察,我们可以发现对于一个确定的n值,函数cut_rod的值也是确定的,我们可以在一次算出结果之后,就将其储存起来,之后使用就可以直接取用

相比于直接暴力搜索,记忆化搜索的的时间复杂度降到了(n^2),可以轻松解决m<10000以内的问题。

int prize[100000]; //价格表
int mem[100000] //记忆化数组 初始为0
int cut_rod(int n)
{    
    if(mem[n])
     return mem[n];//如果搜过了,直接输出结果
    if (n == 0)
        return 0; //没有钢管可切
    int ans = -0x7FFFFFFF;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, prize[i] + cut_rod(n - i));
    }
    return ans;
}

而第二种方法:自底向上法却可以节省更多常数级时间(省去了递归的消耗),因为任何子问题(除了初始子问题)的求解都需要比其更小子问题的结果,不如先把更小的子问题先算出来,然后通过递推的方法一步步的将求解的问题的规模扩大, 先对底层逐个求解,当上层需要调用底层时,底层已经被求解完毕。

vector<int> date;
int m; //价格表的元素数量
int prize[11000];
int BOTTOM_UP_CUT_ROD(int n)
{
    int dp[101000];
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int now = -0x7FFFFFFF;
        for (int j = 0; j < m; j++)
        {
            if (i >= j)
            {
                now = max(now, dp[i - j] + prize[j]);
            }
        }
        dp[i] = now;
    }
    return dp[n];
}

15.2矩阵链乘

15.4最长公共子序列(LCS)

对于给定的两个序列,求解他们两者之间最长的子序列是多少,例如:当第一个序列为 A,B,C,B,D,A,B 第二个序列为 B,D,C,A,B,A 时,他们两者所形成的最长公共子序就为 B,C,B,A 或者 B,D,A,B 。

LCS问题,是存在最优子结构的,因此我们可以在原有基础上往外递推,从而实现状态之间的转移.

如果xm=yn,则zk=xm=yn且Zk是Xm−1和Yn−1的一个LCS。
如果xm≠yn,那么zk≠xm,意味着Z是Xm−1和Y的一个LCS。
如果xm≠yn,那么zk≠yn,意味着Z是X和Yn−1的一个LCS。

因此我们可以据此写出状态转移方程

 if (a[i - 1] == b[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

最后从小到大进行递归便可以进行求解

时间复杂度O(n^2)

空间复杂度O(n^2)(需要一个二维dp数组)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int dp[1000][1000];
int main()
{
    string a, b;
    while (cin >> a >> b)
    {
        for (int i = 0; i <= a.size(); i++)
            for (int j = 0; j <= b.size(); j++)
                dp[i][j] = 0;
        for (int i = 1; i <= a.size(); i++)
        {
            for (int j = 1; j <= b.size(); j++)
            {
                if (a[i - 1] == b[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        cout << dp[a.size()][b.size()] << endl;
    }
    return 0;
}

测试题目 hdoj 1159 Common Subsequence


💭💭💭💭💭💭