LeetCode高级算法之动态规划

深藏阁楼爱情的钟 2022-12-28 04:04 166阅读 0赞

[152. Maximum Product Subarray][]

这题与最大子序列和不同的地方在于, 乘积的状态转移不能用dp\[i-1\]\*num\[i\]来获得, 因为存在负数的情况, 所以这题要用两个dp数组来进行状态转移

maxdp\[i\] = max ( maxdp\[i-1\]\*num\[i\] , mindp\[i-1\]\*num\[i\], num\[i\] )

mindp\[i\] = min (maxdp\[i-1\]\*num\[i\], mindp\[i-1\]\*num\[i\], num\[i\] )

最终结果取maxdp中最大数即可, 考虑到每次的状态转移都是利用前一个数的结果, 可以进行空间优化

[309. Best Time to Buy and Sell Stock with Cooldown][]

与最大买卖股票时机的区别在于多了一个冷冻期, 相当于状态数组多了一个"处于冷冻期"的状态, 剩余的两个状态相同, 为"持有股票", "未持有股票并不处于冷冻期"

状态转移方程有三个, 大致如下

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            const int n = prices.size();
            if (n==0) return 0;
            int hold = -prices[0];    // 持有股票
            int nohold = 0;            // 未持有股票且不在冷冻期
            int cool = 0;                // 未持有股票但是在冷冻期
            int temp1 ,temp2, temp3;
            for (int i=1; i<n; ++i)
            {
                temp1 = max(hold, nohold-prices[i]);    // 现阶段持有股票的最大收益
                temp2 = max(nohold, cool);                
                temp3 = max(cool, hold+prices[i]);
                hold = temp1, nohold = temp2, cool = temp3;
            }
            return max(nohold, cool);
        }
    };

注意每次的状态转移还是利用前一个状态, 所以还是可以进行空间优化

[279. Perfect Squares][]

不考虑数学方法的话, 是很容易想到动态规划的方程的

直接看代码吧

class Solution {
    public:
        int numSquares(int n) {
            if (n<2) return n;
            vector<int>dp(n+1, INT_MAX);
            dp[1] = 1;
            for (int i=2; i<n+1; ++i)
            {
                int root = sqrt(i);
                if (root*root==i) dp[i]=1;    // 恰好是平方数, 答案为1
                else
                {
                    while(root>=1)
                    {
                        int temp = i - root*root;        // 判断减去一个平方数的结果
                        dp[i] = min(dp[i], dp[temp]+1);
                        --root;
                    }
                }
            }
            return dp[n];
        }
        
    };

[139. Word Break][]

[140. Word Break II][]

两道题是一个类型, 139是判断能否拆分, 状态转移方程也很好发现, 我发现leetcode在对0和1的判断中vector<int>速度比vector<bool>快, 相当于用空间换时间了吧

几个关键的数据结构, 一个是哈希表, 快速的找到某子串是否在单词列表内, 一个是string, 灵活运用string的构造函数和substr, 就不会在如何处理字符串上耽误时间

140是要给出所有可行的拆分方案, 显然这类题目离不开回溯法, 而回溯法的定义注定了它是要穷举所有的情况, 时间复杂度为指数级别,

因此这里有个特例就是要用139中的判断是否能拆分来减少一部分工作量, 否则会超时

class Solution {
    public:
        unordered_set<string>mset;
        vector<string> ans;
        void dfs(const string& s, int start, string tp)    // 回溯法找所有的结果
        {
            if (start >= s.length())
            {
                ans.push_back(tp);
                return;
            }
            for (int i=start; i<s.length(); ++i)
            {
                string temp = string(s.begin()+start, s.begin()+i+1);
                if (mset.count(temp))
                {
                    if(tp.empty()) dfs(s, i+1, temp);
                    else dfs(s, i+1, tp + " " + temp);
                }
            }
            return;
        }
        vector<string> wordBreak(string s, vector<string>& wordDict) {
            mset.insert(wordDict.begin(), wordDict.end());
            int max_word_length = 0;
            for (string&s : wordDict)
            {
                max_word_length = max(max_word_length, (int)s.length());    // 找最大单词长度, 可以靠它进行下面的循环部分的优化
            }
            int size = s.length();
            vector<int>dp(size, 0);
            for (int i=0; i<size; ++i)
            {
                string temp = string(s.begin(), s.begin()+i+1);
                if (mset.count(temp)) dp[i] = 1;
                else{
                    for(int j=0; j<i; ++j)
                    {
                        if(i-j>max_word_length) continue;
                        string temp2 = s.substr(j+1, i-j);
                        if (mset.count(temp2) && dp[j]) dp[i] = 1;
                    }
                }
            }
            if(!dp[size-1]) return ans;    // 无法进行拆分, 直接返回空结果
            else{    
                dfs(s, 0, "");    // 可以拆分, 递归回溯
            }
            return ans;
        }
    };

[312. Burst Balloons][]

戳气球是以前没有见过的动态规划, 难点是找到转移方程,  由于每次戳破一个气球整个气球序列的邻居会改变, 一开始怎么也想不到如何写状态转移方程

后来发现这种处理后整体状态改变的题目跟约瑟夫环很相似, 处理方法都是逆向推导, 从结果出发, 那么这样一看就能发现状态转移的写法了,

以最后一个戳掉的气球为例, 此时两边已经没有气球, 可以直接算出它的得分, 戳掉的气球实际上把原气球序列分成了两部分, 两部分各自又有自己的最佳得分,

所以最后的得分就是max(dp\[j\]\[j+i\], full\[j\]\*full\[k\]\*full\[j+i\] + dp\[j\]\[k\] + dp\[k\]\[j+i\])

代码如下:

class Solution {
    public:
        int maxCoins(vector<int>& nums) {
            int size = nums.size();
            vector<int>full={1};
            for (int x:nums) full.push_back(x);
            full.push_back(1);    // full相当于在原序列两边各加一个1
            vector<vector<int>>dp(size+2, vector<int>(size+2, 0));    
            for(int i=2; i<size+2; ++i)    // 以间隔2开始, 每次增加间隔dp
            {    
                for (int j=0; i+j<size+2; ++j)
                {
                    for (int k=j+1; k<j+i; ++k)
                    {
                        dp[j][j+i] = max(dp[j][j+i], full[j]*full[k]*full[j+i] + dp[j][k] + dp[k][j+i]);        // 注意这里是full[j]*full[k]*full[j+i] 而不是full[k-1]*full[k]*full[k+1]
                    }
                }
            }
            return dp[0][size+1];
        }
    };

[152. Maximum Product Subarray]: https://leetcode-cn.com/problems/maximum-product-subarray/
[309. Best Time to Buy and Sell Stock with Cooldown]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[279. Perfect Squares]: https://leetcode-cn.com/problems/perfect-squares/
[139. Word Break]: https://leetcode-cn.com/problems/word-break/
[140. Word Break II]: https://leetcode-cn.com/problems/word-break-ii/
[312. Burst Balloons]: https://leetcode-cn.com/problems/burst-balloons/