动态规划5：动态规划与记忆化搜索

p_wh

3704人浏览 · 2022-02-09 12:10:28

p_wh · 2022-02-09 12:10:28 发布

本期题目：

单词拆分

单词拆分II

大礼包

记忆化搜索与狭义的动态规划

前面我们讲的动态规划很广义的思想，从起始时刻到终止时刻，每一步都要按照最优原则走，按照这个原则会产生一个迭代式，称为动态规划迭代方程或者叫状态转移方程，而求解动态规划递归方程的方法则没有一个定式。

在动态规划I中我们讲到，如果直接采用暴力迭代的方法，时间复杂度会非常高，和暴力穷举区别不大，原因在于迭代过程会产生大量的重复计算，为了避免重复计算，我们前面采取的办法都是从终点向起点倒推，计算所有状态的价值函数，倒推到起点，就能求解出状态转移方程。

当然，在某些情况下这也不是最优的解法，因为不是所有状态的价值函数都需要计算，也就是说，可能存在“多余计算”的问题。此时，我们不如就按照状态转移方程进行递归，已经计算过的一些价值函数的值储存起来以避免重复计算，这样我们就可以在计算最少的价值函数的情况下求解状态转移方程。这是一种从起点到终点的计算方法，最差情况是需要计算全部的价值函数，但如果我们有一些原则可以排除不可能的路径，那需要计算的价值函数的数量就大大减少。计算全部价值函数的实现方法我们称为狭义的动态规划，后面简称为动态规划。动态规划和记忆化搜索都是动态规划算法的实现方法，各有利弊。

动态规划的优缺点： 由于迭代式通常不涉及所有后续的时刻，所以采用动态规划的方法来实现通常可以对动态规划数组进行降维，在保持时间复杂度不变的情况下，能有效降低空间复杂度（见动态规划2-4的所有题目）。并且，由于动态规划方法不涉及递归，不需要回溯。其缺点是需要计算所有状态的价值函数。

记忆化搜索的优缺点： 记忆化搜索的优点在于不需要计算所有状态的价值函数，相当于对整个递归过程进行剪枝，其最差复杂度和动态规划方法是一个量级。其缺点是虽然可能不需要计算所有状态价值函数，但很多问题通常都需要计算所有状态价值函数的值，而记忆化搜索还有一个回溯的过程，在需要计算大多数状态价值函数值时记忆化搜索不一定能比动态规划要快，甚至可能比动态规划要慢。并且，尽管我们不需要计算所有状态的价值函数，但是为了检索方便通常以哈希表储存，要分配所有价值函数的空间，空间复杂度一般比动态规划方法要大。

我们可以以计算斐波那契数列为例来说明为什么记忆化搜索相当于对递归过程进行剪枝，如果用暴力递归的方法计算斐波那契数列，C++代码如下

int f(int n){
  if(n==1) return 1;
  else if(n==2) return 2;
  else return f(n-1)+f(n-2);
}

其时间复杂度很容易计算出来是指数的，整个递归树如下图所示：
斐波那契数列递归图

按照调用顺序，我们先调用f(n-1)，而f(n-1)会先调用f(n-2)，如果我们在第一次计算完f(n-2)之后储存起来，储存在dp[n-2]中，那么第二次调用f(n-2)时，不需要再走一遍递归过程，原本f(n)的右子树还有一大棵迭代书，因为记忆化搜索被全部剪掉，于是时间复杂度计算的差分方程变为 $t (n) = t (n - 1) + 1$
此时，时间复杂度从 $O(2^n)$ 降低到 $O (n)$ ，这就是记忆化搜索减小时间复杂度的基本原理。

单词拆分问题（139和140）

[139.单词拆分问题]是一个记忆化搜索可能优于动态规划，那么我们来决定状态空间和行为空间。第一步我们要决定最左边的单词是什么？由于题目给出的最大单词的长度为20，我们可以分别试探子列s.substr(0,len)(len=1,2,…,20)是否在字典wordDict中，如果不在，那么第一个单词一定不是这个，如果在，则看后续的序列能不能被拆分。那么状态就定义为剩余的序列，行为是拆出哪些单词，终止条件是确定不能再拆分，或者单词被拆分完毕，那么递归方程就是 $dp[i]=dp[i]\lor (wordAtDict(i,j,wordDict) \land dp[i+j])\quad i+j\leq n-1,j=1,2,\cdots,20$

由于或运算的原则是只要有一个命题为真就为真，实际上，我们可以直接从最大长度进行验证，如果直接找到一种拆分方法，其他的拆分方法都可以不再分析，这可以大大缩小我们的搜索范围，从而可能找到比动态规划更高效的方法，以下为动态规划方法的代码。

/*动态规划求解单词拆分问题，未进行空间复杂度优化*/
class Solution {
public:
    void sort(vector<string>& wordDict,int begin,int end){
        if(end-begin==0) return;
        else if(end-begin==1){
            if(wordDict[begin]>wordDict[end]){
                string temp = wordDict[begin];
                wordDict[begin] = wordDict[end];
                wordDict[end] = temp;
            }
        }
        else{
            int mid = (end+begin)/2;
            sort(wordDict,begin,mid);
            sort(wordDict,mid+1,end);
            int ptr1 = begin;
            int ptr2 = mid+1;
            vector<string> tmp(end-begin+1,"");
            for(int i=0;i<=end-begin;i++){
                if(ptr1<=mid){
                    if(ptr2<=end){
                        if(wordDict[ptr1]>wordDict[ptr2]){
                            tmp[i] = wordDict[ptr2];
                            ptr2++;
                        }else{
                            tmp[i] = wordDict[ptr1];
                            ptr1++;
                        }
                    }else{
                        tmp[i]=wordDict[ptr1];
                        ptr1++;
                    }
                }else{
                    if(ptr2<=end){
                        tmp[i] = wordDict[ptr2];
                        ptr2++;
                    }
                }
            }
            for(int j=0;j<=end-begin;j++){
                wordDict[begin+j]=tmp[j];
            }
        }
    }
    bool wordAtDict(const string& s,vector<string>& wordDict,int begin,int end){
        string word = s.substr(begin,end-begin+1);
        int n = wordDict.size();
        if(wordDict[n-1]==word) return true;
        if(wordDict[0]==word) return true;
        int left = 0;
        int right = n-1;
        int mid = (right+left)/2;
        while (right-left>=2)
        {
            if(word==wordDict[mid]) return true;
            else if(wordDict[mid]<word) left = mid;
            else right = mid;
            mid = (right+left)/2;
        }
        return (word==wordDict[left])||(word==wordDict[right]);
    }
    bool wordBreak(string s,vector<string>& wordDict){
            /*记号 n=s.size(),m=wordDict.size()*/
        int n = s.size();
        int m = wordDict.size();
        /*1. 对wordDict进行排序，从而方便进行二分查找*/
            /*排序复杂度 字符串比较O(1),排序 mlog(m) */
            /*排序方法：归并排序*/
        sort(wordDict,0,m-1);
        /*2. 动态规划*/
            /*动态规划复杂度，nlog(m)，总时间复杂度(n+m)log(m)*/
        if(n==1) return wordAtDict(s,wordDict,0,0);
        else{
            vector<bool> dp(n,false);
            dp[n-1] = wordAtDict(s,wordDict,n-1,n-1);
            for(int i=n-2;i>=0;i--){
                int j=0;
                while(i+j<=n-2&&j<=20){
                    if(dp[i+j+1]&&wordAtDict(s,wordDict,i,i+j)){
                        dp[i] = true;
                        break;
                    }
                    j++;
                }
                if(i+j==n-1) dp[i]=dp[i]||wordAtDict(s,wordDict,i,n-1);
            }
            return dp[0];
        }
    }
};

复杂度分析见代码的wordBreak函数，空间复杂度 $O (n)$

记忆化搜索的代码如下：

class Solution {
private:
    int n;
    int m;
    vector<bool> dp,dp2;//dp用来保存已经计算的结果，dp2用于记录该结果是不是已经计算过
    bool wordAtDict(const string& s,const vector<string>& wordDict,int begin,int len){
        string word = s.substr(begin,len);
        if(word<wordDict[0]) return false;
        else if(word>wordDict[m-1]) return false;
        else{
            int l = 0;
            int r = m-1;
            int mid=(l+r)/2;
            while(r>=l+2){
                if(word==wordDict[mid]) return true;
                else if(word>wordDict[mid]) l=mid;
                else r=mid;
                mid=(l+r)/2;
            }
            return (word==wordDict[l])||(word==wordDict[r]);
        }
    }
    void sort(vector<string>& wordDict,int begin,int end){
        if(end-begin==0) return;
        else if(end-begin==1){
            if(wordDict[begin]>wordDict[end]){
                string temp = wordDict[begin];
                wordDict[begin] = wordDict[end];
                wordDict[end] = temp;
            }
        }
        else{
            int mid = (end+begin)/2;
            sort(wordDict,begin,mid);
            sort(wordDict,mid+1,end);
            int ptr1 = begin;
            int ptr2 = mid+1;
            vector<string> tmp(end-begin+1,"");
            for(int i=0;i<=end-begin;i++){
                if(ptr1<=mid){
                    if(ptr2<=end){
                        if(wordDict[ptr1]>wordDict[ptr2]){
                            tmp[i] = wordDict[ptr2];
                            ptr2++;
                        }else{
                            tmp[i] = wordDict[ptr1];
                            ptr1++;
                        }
                    }else{
                        tmp[i]=wordDict[ptr1];
                        ptr1++;
                    }
                }else{
                    if(ptr2<=end){
                        tmp[i] = wordDict[ptr2];
                        ptr2++;
                    }
                }
            }
            for(int j=0;j<=end-begin;j++){
                wordDict[begin+j]=tmp[j];
            }
        }
    }
    bool wordBreak(const string& s,const vector<string>& wordDict,int begin){
        int len=min(20,n-begin);
        if(dp2[begin]) return dp[begin];
        else dp2[begin]=true;
        while(!dp[begin]&&len>=1){
            if(begin+len<n){
                dp[begin]=wordAtDict(s,wordDict,begin,len)&&wordBreak(s,wordDict,begin+len);
            }else{
                dp[begin]=wordAtDict(s,wordDict,begin,len);
            }
            len--;
        }
        return dp[begin];
    }
public:
    bool wordBreak(const string& s, vector<string>& wordDict) {
        /****方法2:记忆化搜索****/
        n=s.size();
        m=wordDict.size();
        //对wordDict进行排序
        sort(wordDict,0,m-1);
        //初始化dp和dp2
        dp=vector<bool>(n,false);
        dp2=vector<bool>(n,false);
        //迭代
        return wordBreak(s,wordDict,0);
    }
};

[140.单词拆分问题II]也是类似的，就是选择最左边要拆分出来的单词，如果在字典内，则拆分出来，和后面的拆分方法拼接在一起就成了一种拆分方法，这个问题自然要遍历所有的状态，所以，即便是使用记忆化搜索也无法优化时间复杂度，但记忆化搜索通常采用递归的形式，更直观一些，下边给出记忆化搜索的代码，动态规划的代码可以相应地做修改。

class Solution {
private:
    int n,m,minlen,maxlen;
    vector<vector<string>> dp;
    vector<bool> dp2;
    bool wordAtDict(const string& s,const vector<string>& wordDict,int begin,int len){
        string word = s.substr(begin,len);
        if(word<wordDict[0]) return false;
        else if(word>wordDict[m-1]) return false;
        else{
            int l = 0;
            int r = m-1;
            int mid=(l+r)/2;
            while(r>=l+2){
                if(word==wordDict[mid]) return true;
                else if(word>wordDict[mid]) l=mid;
                else r=mid;
                mid=(l+r)/2;
            }
            return (word==wordDict[l])||(word==wordDict[r]);
        }
    }
    void sort(vector<string>& wordDict,int begin,int end){
        if(end-begin==0) return;
        else if(end-begin==1){
            if(wordDict[begin]>wordDict[end]){
                string temp = wordDict[begin];
                wordDict[begin] = wordDict[end];
                wordDict[end] = temp;
            }
        }
        else{
            int mid = (end+begin)/2;
            sort(wordDict,begin,mid);
            sort(wordDict,mid+1,end);
            int ptr1 = begin;
            int ptr2 = mid+1;
            vector<string> tmp(end-begin+1,"");
            for(int i=0;i<=end-begin;i++){
                if(ptr1<=mid){
                    if(ptr2<=end){
                        if(wordDict[ptr1]>wordDict[ptr2]){
                            tmp[i] = wordDict[ptr2];
                            ptr2++;
                        }else{
                            tmp[i] = wordDict[ptr1];
                            ptr1++;
                        }
                    }else{
                        tmp[i]=wordDict[ptr1];
                        ptr1++;
                    }
                }else{
                    if(ptr2<=end){
                        tmp[i] = wordDict[ptr2];
                        ptr2++;
                    }
                }
            }
            for(int j=0;j<=end-begin;j++){
                wordDict[begin+j]=tmp[j];
            }
        }
    }
    void wordBreak(const string& s,const vector<string>& wordDict,int begin){
        if(dp2[begin]) return;
        else dp2[begin]=true;
        for(int len=minlen;len<=maxlen&&begin+len-1<=n-1;len++){
            string word = s.substr(begin,len);
            if(begin+len==n&&wordAtDict(s,wordDict,begin,len)){
                dp[begin].push_back(word);
            } 
            else if(dp2[begin+len]){
                if(wordAtDict(s,wordDict,begin,len)){
                    for(const auto& str:dp[begin+len]){
                        dp[begin].push_back(word+" "+str);
                    }
                }
            }else{
                wordBreak(s,wordDict,begin+len);
                if(wordAtDict(s,wordDict,begin,len)){
                    for(const auto& str:dp[begin+len]){
                        dp[begin].push_back(word+" "+str);
                    }
                }
            }
        }
    }
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n=s.size();
        m=wordDict.size();
        //排序
        sort(wordDict,0,m-1);
        minlen=wordDict[0].size();
        maxlen=wordDict[0].size();
        for(const auto& str:wordDict){
            int n0=str.size();
            minlen=min(minlen,n0);
            maxlen=max(maxlen,n0);
        }
        //记忆化搜索
        dp=vector<vector<string>>(n,vector<string>());
        dp2=vector<bool>(n,false);
        wordBreak(s, wordDict, 0);
        //返回结果
        return dp[0];
    }
};

638. 大礼包问题

大礼包问题是一个记忆化搜索可以大展身手的问题，我们的状态就定义为需求，行为是购买哪个大礼包或购买哪个单品，一次只购买一个单品或者一个大礼包，终止条件是刚好满足需求，状态转移方程也很容易推导。

现在，我们来看，如果购买某个大礼包会有优惠，那么购买这个大礼包，其他再用单品补充，一定比购买单品要划算，因此，如果能够购买优惠大礼包，那么最优选择一定含有一个优惠大礼包，如果不能购买任何一个优惠大礼包，那么剩下则是全部购买单品，成本可以直接算出。所以我们的行为空间缩小至购买哪个优惠大礼包（注意：这里反复加入定语优惠大礼包，说明有优惠这个礼包才能加入行为空间），这样就对递归树进行剪枝，大大减少时间复杂度。

由于需求是一个多维数组，并且维度不同的问题略有不同，因此我们选择用一个一维数组储存所有值，通过一个一对一的函数映射到多维需求中，这样我们应用记忆化搜索再无障碍，记忆化搜索代码如下：

class Solution {
private:
    vector<int> dp,shape;
    //shape用于方便计算映射
    vector<bool> packageCanbuy;//用来记录这个礼包是否有优惠
    int n,m,CostSingle;//CostSingle是全部单件购买的成本
    //n为物品件数，m是大礼包数量
    //needToIndex函数是给定needs找到其在dp数组的位置，是一个一对一的映射
    int needToIndex(const vector<int>& needs){
        int result=0;
        for(int i=0;i<n;i++) result+=needs[i]*shape[i];
        return result; 
    }
    //递归函数
    int shoppingOffers_(vector<int>& price,vector<vector<int>>& special,const vector<int>& needs){
        if(dp[needToIndex(needs)]>=0) return dp[needToIndex(needs)];
        else{
            int minCost=CostSingle;
            vector<int> need2=needs;
            bool buybyPackage = false;
            //优先礼包购买
            for(int i=0;i<m;i++){
                if(!packageCanbuy[i]) continue;
                bool canBuy=true;
                int p = special[i][n];
                for(int j=0;j<n;j++){
                    need2[j]-=special[i][j];
                    if(need2[j]<0){
                        canBuy=false;
                        break;
                    }
                }
                if(canBuy){
                    buybyPackage=true;
                    minCost=min(minCost,p+shoppingOffers_(price, special, need2));
                }
                need2=needs;
            }
            if(buybyPackage){
                dp[needToIndex(needs)]=minCost;
                return minCost;
            }
            //如果不能用任何优惠礼包购买，那么直接全部单件购买
            int index =needToIndex(needs);
            dp[index]=0;
            for(int i=0;i<n;i++){
                dp[index]+=price[i]*needs[i];
            }
            return dp[index];    
        }
    }
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        n=price.size();
        int prd=1;
        shape = vector<int>(n,0);
        CostSingle=0;
        for(int i=0;i<n;i++){
            shape[i]=prd;
            CostSingle+=price[i]*needs[i];
            prd*=(needs[i]+1);
        }
        dp = vector<int>(prd,-1);
        dp[0]=0;
        m = special.size();
        packageCanbuy=vector<bool>(m,true);
        for(int i=0;i<m;i++){
            int p=special[i][n];
            int c=0;
            for(int j=0;j<n;j++) c+=price[j]*special[i][j];
            packageCanbuy[i]=(p<c);
        }
        return shoppingOffers_(price, special, needs);
    }
};