动态规划详解

<span style="font-family: Tahoma; background-color: rgb(255, 255, 255);">      其实根本就谈不上详解，应该说只是随便谈谈，真正能详解动态规划的又有几个人，所以，这个标题略显扯淡。</span>

前段时间一直在做关于数据结构的题，也算是对数据结构有了一定的了解，知道了有些数据结构的基本算法。现在刚刚开始接触动态规划，其实写这篇文章的初衷是一来锻炼一下自己的总结能力，二来也是希望通过这篇文章，来指引和我一样的初学者，废话不多说了，开始吧。

一、01背包

我最开始接触的有关动态规划的是01背包，这应该也是动态规划入门最好的了吧。 01背包是很简单的问题，当然也不乏一些变种让你绞尽脑汁也想不到，这里我们不讨论那些，我只说最简单的。

假设有n种物品，每种都只有一个，第i种物品的体积为Vi，重量为Wi，选一些物品到一个容量为C的背包，使得背包内总物品的体积不超过C的情况下重量最大。

因为每种东西只有放入背包和不放入两种状态，这也就是01的由来了。对于这个问题，你当然可以枚举所有的可能性，如果有n个物品的话，总共有2^n种可能性，如果数据大的话，普通计算机是不可能计算的，当然你可以借一台超级计算机，这是另外一种情况，不予讨论。

我们可以换一种思考方法，对与第i件物品，我们比较把它放入和不放入背包中的重量比较，取最大值，这样我们就可以得到这样一个表达式 dp(V) = max(dp(V), dp(V-vi) + wi)，具体实现我们可以采用递归的方式。这样时间复杂度好会不会好很多，很明显不会，因为会重复计算好多次，举个简单例子，如果我们计算dp(6)，在这个过程中我们用到了dp(3)，而在计算dp(5)的过程中也用到了dp(3)，这样这两个过程就会重复计算一次dp(3)，想想数据量大的话该有多少重复啊。。

关于这个重复计算的问题，我们只要在过程中记录这些结果就完全可以避免重复计算，还是上面的例子，我们在dp(6)中计算了dp(3)，并且将dp(3)的结果保存了，在dp(5)中我们直接调用dp(3)，就行了，这种方法被称为记忆化搜索，因为dp()这个函数你在一定程度上可以把它当做dfs()。

虽然记忆话搜索就是动态规划的思想，不过这还不是最好的方法，我们完全可以把递归改成递推的方式，这样dp[V] = max(dp[V], dp[V-vi] + wi)，这个表达式也被称为状态转移方程，这也是动态规划的核心，还有，一定要理解01背包这个方程，因为绝大多数状态转移方程是由它演变来的。

我们不难写出递推的代码

for (int i = 1; i <= n; i++)
{
    for (int j = C; j >= v[i]; j--)
    {
        dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
    }
}

时间复杂度为O(n*n)，时间上我们没办法在优化了，但在空间上我们可以继续优化，我们可以把dp数组改成一维的，得到以下代码也是正确的，因为在求解的过会覆盖掉一部分，但覆盖之后的值却是该状态的最优解。

for (int i = 1; i <= n; i++)
{
    for (int j = C; j >= v[i]; j--)
    {
        dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
    }
}

二、最长非降子序列

这个也比较简单，也是基本的东西，不过越基本的越应该熟悉。

我们让dp[i] 保存前i个数的最长非降子序列长度，每次计算以第i个数结尾的最长子序列的长度。状态转移方程就是dp[i] = max(dp[i],dp[j] + 1)。

#include <stdio.h>
#include <string.h>

int a[100];
int dp[100];
int max(int a, int b)
{
    return a > b ?a : b;
}

int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] > a[j])
                dp[i] = max(dp[i],dp[j] + 1);
        }
    }
    printf("%d\n",dp[n]);
}

三、最长公共子序列（LCS）

动态规划就是求最优子问题，通过局部最优值来推导全局最优。

先说一下什么是最长公共子序列，比如BDCAB 和 ABCBA两个字符串，他们的最长公共子序列是 BCBA，长度为4。这里要注意区分字串和子序列，字串要求连续，而子序列不要求连续。

接下来说一下解法

求解最长公共子序列肯定是求解全局最优的问题，可以通过逐步推到求出。这里我们需要定义一个数组dp[i][j], 数组中的结果表示第一个字符串从1-i位置和第二个字符串从 1-j位置最长公共子序列（需注意这里字符串下标是从1开始的）。

注意看以下这张图，这是理解LCS 问题的关键，途中每个格子里的值表示到这个下标对于字符串最长公共子序列的长度。我们可以通过dp[i-1][j], dp[i-1][j-1], dp[i][j-1], 这三个格子来推导dp[i][j], 具体方法是，如果两个字符串中对应的 i 和j位置（s[i] 和 t[j]，图中竖着为s 横为t）相同，那么dp[i][j] = dp[i-1][j-1]+1,因为比 i-1 j-1 对应的字符串多了一个相同的字符，如果不同，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，在图中就是dp[i][j] 左边和上边的格子。

图中每个格子都有一个箭头，表示的是格子中的值是通过哪个格子计算出来的。

用dp数组只能计算出两个字符串最长公共子序列的长度，并不能求出这个公共子序列。当然这也是可以求出的，再来看这图，灰色的格子中斜着的箭头所在格子对应的字符按顺序组合就是他们最长公共子序列，当然这不是巧合，我们只需要额外开一个数组来记录这个箭头就可以了。不是什么难事。

以下是代码：

int LCS(char* s, char* t)
{
    int dp[MAX][MAX];
    int n = strlen(s);
    int m = strlen(t);
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (s[i-i] == t[j-1])   //计算的时候下标要从1开始，这里做一下相应的转换
                dp[i][j] = dp[i-1][j-1]+1;
            else 
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[n][m];
}

此文章将持续更新。。。。。。

秒客网

动态规划详解

相关文章