动态规划算法

最近忙于校招，好长时间没写博客了。鉴于这几天的笔试特别多，而且很多的笔试题和动态规划算法相关，因此再次复习复习这个算法。

动态规划算法的关键之处在于用一个一维或二维数组来保存已经计算出来的结果，避免了重复的计算，因此将很多指数级的时间复杂度降低到了多项式级别。而光满足这一点还不能称之为动态规划，最多只能称为“记忆搜索”的算法。动态规划是在记忆搜索的基础上，限制了计算的次序，以自底向上的方式来计算。

来看几个动态规划的经典例子：

最长公共子序列问题

给定两个字符串，求他们的最长公共子序列的长度。

int LCS(const string& str1, const string& str2)
{
    vector<vector<int> > dp(str1.size() + 1, vector<int>(str2.size() + 1, 0));
    int i, j;
    for (i = 0;i <= str1.size();++i)
    {
        for (j = 0;j <= str2.size();++j)
        {
            if (i == 0 || j == 0)
            {
                dp[i][j] = 0;
            }
            else
            {
                if (str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[i - 1][j - 1];
}

最少编辑问题

给定两个字符串，可以对其中一个进行insert，delete，replace三种操作，请问最少需要多少次操作可以使两个字符串相同？

int getmin(int a, int b, int c)
{
    int min = a > b ? b : a;
    min = min > c ? c : min;
    return min;
}

void SE(const string& str1,const string& str2)
{
    vector<vector<int> > dp(str1.size()+1, vector<int>(str2.size()+1, 0));
    int i, j;
    dp[0][0] = 0;
    for (i = 0;i < dp.size();++i)
    {
        for (j = 0;j < dp[i].size();++j)
        {
            if (i == 0 &amp;&amp; j == 0)
                continue;
            if (i == 0 || j == 0)
            {
                if (i == 0)
                    dp[i][j] = dp[i][j - 1] + 1;
                else
                    dp[i][j] = dp[i - 1][j] + 1;
            }
            else
            {
                int a = dp[i - 1][j] + 1;
                int b = dp[i][j - 1] + 1;
                int c ; 
                if (str1[i - 1] != str2[j - 1])
                    c = dp[i - 1][j - 1] + 1;
                else
                    c = dp[i - 1][j - 1];
                int min = getmin(a, b, c);
                dp[i][j] = min;
            }
        }
    }
    return dp[dp.size() - 1][dp[0].size() - 1];
}