动态规划二-阿里云开发者社区

复杂一些的线性动态规划:买卖股票系列问题

121.买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // int n=prices.size();
        // int max1=0;
        // for(int i=0;i<n;i++)
        // {
        //     for(int j=i+1;j<n;j++)
        //     {
        //         if(prices[i]<prices[j])
        //         {
        //             max1=max(prices[j]-prices[i],max1);
        //         }
        //     }
        // }
        // return max1;
        int n=prices.size();
        int min_pre=INT_MIN;
        int max1=0;
        for(int i=0;i<n;i++)
        {
            min_pre=max(min_pre,-prices[i]);
            max1=max(max1,min_pre+prices[i]);
        }
        return max1;
    }
};

122.买卖股票的最佳时机Ⅱ

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++){
            ans += max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
};

123.买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

188.买卖股票的最佳时机IV

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<2)
        {
            return 0;
        }
        if(k>=n)
        {
            return GetMaxProfit(prices);
        }
        vector<int> buy(n+1,INT_MIN),sell(n+1,0);
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<k+1;j++)
            {
                buy[j]=max(buy[j],sell[j-1]-prices[i-1]);
                sell[j]=max(sell[j],buy[j]+prices[i-1]);
            }
        }
        return sell[k];
    }
    int GetMaxProfit(vector<int>& prices)
    {
        int maxProfits=0;
        for(int i=1;i<prices.size();i++)
        {
            if(prices[i]>prices[i-1])
            {
                maxProfits+=prices[i]-prices[i-1];
            }
        }
        return maxProfits;
    }
};

714.买卖股票的最佳时机含手续费

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        vector<int> sell(n,0);
        vector<int> buy(n,0);
        buy[0]=-prices[0];
        for(int i=1;i<n;i++)
        {
            buy[i]=max(buy[i-1],sell[i-1]-prices[i]);
            sell[i]=max(sell[i-1],buy[i-1]+prices[i]-fee);
        }
        return sell[n-1];
    }
};

309.最佳买卖股票时机含冷冻期

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n= prices.size();
        if(n==0)
            return 0;
        vector<int> sell(n),buy(n),s1(n),s2(n);
        buy[0]=s1[0]=-prices[0];
        sell[0]=s2[0]=0;
        for(int i=1;i<n;i++)
        {
            buy[i]=s2[i-1]-prices[i];            
            s1[i]=max(s1[i-1],buy[i-1]);
            sell[i]=max(s1[i-1],buy[i-1])+prices[i];
            s2[i]=max(s2[i-1],sell[i-1]);
        }
        return max(sell[n-1],s2[n-1]);
    }
};

题目模型

拿到题目第一步，提取关键信息

这些题目大同小异，共同点在于:

任何时刻最多只能持有1股

不同点在于:

交易次数限制（1次、2次、c次、无限次)
是否有手续费
是否有冷冻期

定义状态

拿到题目第二步，人工模拟

把自己代入这个股票交易的情景，你会怎么做?需要关注哪些事情?

今天几号?——决定了股票价格
当前持仓（有没有股票? )——知道这个，才能知道接下来该买还是该卖
已经交易了多少次?——如果有交易限制，得计好数
在不在冷冻期内?——知道这个，才能知道当日可否交易
手续费是一个固定的值，随着交易出现，没必要特别关注（影响计算公式，不影响状态)

人工模拟时关注的变化信息，就是DP需要维护的状态

i:天数，j:持仓（0或1) ， k:已交易次数，l:是否在冷冻期（0或1)

简化版状态转移方程

fli.j]表示第i天结束时，持有j股股票（0或1）的最大收益

决策（表示更新max) :

买:ft,1] - f [i -1,0]- prices[i]
卖:fli,0] - f[i-1,1]+prices[i]
啥也不干:fLi,j]- f[i-1,j]

边界:f[0,0]=0，其余负无穷

最优性的动态规划问题，数组从1开始算（1~n天)，0作为边界，没算过/不合法的状态一律赋值为士o，有助于省去各种复杂的边界判断

目标:f [n,0]

时间复杂度:0(n)

状态转移方程

f[i,j,k]表示第i天结束时，持有j股股票（0或1)，已经交易了k次的最大收益

决策（一表示更新max) :

买: f[i,1,k]- f [i-1,0,k -1]- prices[i]
卖:f[i,0,k] - f [i -1,1,k ]+ prices[i]
啥也不干:f[i,j,k]- f[i一1, j, k]

边界:f[0,0,0]=0，其余负无穷

最优性的动态规划问题，数组从1开始算（1~n天)，0作为边界，没算过/不合法的状态一律赋值为士oo，有助于省去各种复杂的边界判断

C++ Code

Java Code

Python Code

终极版状态转移方程

f [i, j,k,l]表示第i天结束，持有j股股票（O或1)，已经交易了k次，冷冻期状态为l(0-正常，1-冷冻期)时的最大收益

决策:

买: f [i,1,k,0]- f [i一1,0, k - 1,0]- prices[i] - fee
卖:f [i, 0,k,1]- f[i一1,1,k,0] + prices[i]
啥也不干: f [i, j,k,0]- f [i-1, j ,k,l]，其中l=0或1

思考1:与贪心的对比

无交易次数限制，可贪心

当前持有股票，卖不卖?往后看一天，明天还涨那肯定不卖，明天跌那肯定卖啊!——往后看一天就知道今天怎么操作，局部最优可推出全局最优

有交易k次限制，不能贪心

“明天跌那肯定卖啊”这个策略不再正确，也许明天小幅回调，后天继续大涨，卖出将会消耗一次交易机会，可能导致后续无法再交易
——往后看到底才有可能知道今天怎么操作，决策是基于全局考量的

贪心题都能用动态规划做，只不过时间复杂度可能会差一些

以后拿到题目不要再从贪心开始想了

蛮力搜索—(同类子问题)—>分治—(最优子结构)—→动态规划，这才是一条自然的解题路线

思考2∶状态与决策的平衡选择

在简化版状态转移方程中，f[i,j]表示第i天结束时，持有j股股票（O或1）的最大收益

有的同学可能会问:既然若干次交易是不交叉的，为什么不用f[i]表示第i天结束（并恰好完成一笔交易)时的最大收益?

也就是考虑上一次交易是在何时(j）完成的，在j+1~i-1之间选一天(k)买入，在i卖出可以看到状态虽然得到了一点点简化，但决策变得非常复杂（需要枚举)，时间复杂度反而上升了

这涉及到状态与决策之间的一个平衡选择，**状态包含的信息越多，决策越简单;状态越简单，**决策越复杂一般我们解题时，尽量把人工模拟时关注的信息都放到状态里，除非最后状态规模太大，再考虑简化

思考3:状态转移方程的两种写法

在一些决策比较复杂的题目中，考虑“f[i][][k][]该怎么计算?”会比较难

其实状态转移还有另外一种考虑方式:“f[i][][k][1]能更新哪些状态?”

D的本质还是对状态空间的遍历，这两个的区别就像“谁能走到我”和“我能走到谁”大家可以自由选择，哪个想起来比较顺，就用哪个

状态转移方程不好写，可以用列表法

思考4:空间的优化

仔细观察状态转移方程，f [,?,?,?]总是从f[i一1,?,?,?]转移过来，与更早的i-2,i-3,.没有关系

如果把每个f[i]看作一行，那么转移只在相邻两行之间发生

这种情况下可以使用滚动数组优化

实现中，先不优化，写完以后在每个f 的第一维加个&1 (and 1，即mod 2)

注意初始化复用的空间

滚动数组:演示

以简化版状态转移方程为例，f[i,j]表示第i天结束时，持有j股股票（0或1)的最大收益prices = [7,1,5,3,6,4]

思考5:d天冷冻期?

多了什么信息，往状态里放就好了…

fli, j,k,l]表示第i天结束，持有j股股票（O或1)，已经交易了k次，冷冻期还有Ⅰ天时的最大收益

思考6∶最多持仓t股股票?

如果每天只能买卖1股

f l[i, j,k,l]表示第i天结束，持有j股股票，已经交易了k 次，冷冻期还有l天时的最大收益

如果每天可以买卖≤t股

仔细思考一下可以发现，每次交易必然以t股为单位最优，j要么为0，

要么为t——贪心优化了DP

复杂一些的线性DP实战

198.打家劫舍

https://leetcode.cn/problems/house-robber/

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1) return nums[0];
        vector<int> dp(n+1,0);
        dp[0]=nums[0];
        dp[1]=nums[0]>nums[1]?nums[0]:nums[1];
        for(int i=2;i<n;i++)
        {
            dp[i]=dp[i-1]>dp[i-2]+nums[i]?dp[i-1]:dp[i-2]+nums[i];
        } 
        //return acculumate(dp.begin(),dp.end(),1);
        return dp[n-1];
    }
};

把自己代入小偷的情景，关注的信息:

偷到哪个屋子了
刚刚那座房子进没进去

fli,j]表示计划偷窃前i座房屋，第i座房屋的闯入情况为j（O-未闯入，1-闯入）时的最大收益

f [ ,0]= max(f[i -1,1],f [i -1,0])

f[i,1]= f [i 一1,0]+ nums[i]

初值:f[0,0]= 0，f[0,1]= -co

目标: max(f [n,0], f [n,1])

213.打家劫舍Ⅱ

https://leetcode.cn/problems/house-robber-ii/

class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int first = nums[start], second = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
    int rob(vector<int>& nums) {
        int length = nums.size();
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return max(nums[0], nums[1]);
        }
        return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }
};

状态转移只在相邻两个阶段发生，我们把它称为“滚动型”DP

“滚动型DP”处理环的方法——两次DP

第一次:不偷1，可以偷n

初值:f[1,0]=0,f[1,1] =-oo，目标:max(f [n,0], f [m, 1])

第二次:不偷n，可以偷1

初值:f [1,0]= 0,f[1,1]= nums[1]，目标:f [n,0]

状态转移方程与一般的线性DP相同

原理:“滚动型”的环断开一条边，这条边一般只有两种情况，分别求一下取最优就行了

72.编辑距离

https://leetcode.cn/problems/edit-distance/

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n=word1.length();
        int m=word2.length();
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i=0;i<n+1;i++)
        {
            for(int j=0;j<m+1;j++)
            {
                if(i==0)
                {
                    dp[i][j]=j;
                }
                else if(j==0)
                {
                    dp[i][j]=i;
                }
                else
                {
                    dp[i][j]=min(dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1),min(dp[i][j-1]+1,dp[i-1][j]+1));
                }
            }
        }
        return dp[n][m];
    }
};

背包

0/1背包

给定N个物品，其中第i个物品的体积为Vi，价值为W

有一容积为M的背包，要求选择一些物品放入背包，使得物品总体积不超过M的前提下，物品的价值总和最大

0/1背包（C++ Code)

0/1背包（优化版)

416.分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/

物品: nums中的数体积:数值

价值:无（不再是最优化问题，而是可行性问题，DP数组的值是true/false)

能否凑成sum/2这个体积?

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        int target=sum/2;
        if(sum&1==1){
            return false;
        }
        int max_num=*max_element(nums.begin(),nums.end());
        if(max_num>target){
            return false;
        }
        int n=nums.size();
        vector<vector<bool>> dp(n+1,vector<bool>(target+1,false));
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=true;
        }
        //dp[0][nums[0]]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=target;j++)
            {
                if(j>=nums[i-1])
                {
                    dp[i][j]=dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }else{
                    dp[i][j]=dp[i-1][j];
                }            
            }
        }
        return dp[n][target];
    }
};

完全背包

给定Ⅳ种物品，其中第i种物品的体积为V，价值为W，并且有无数个

有一容积为M的背包，要求选择若干个物品放入背包，使得物品总体积不超过M的前提下，物品的价值总和最大

完全背包（优化版)

实战:零钱兑换Ⅱ

https://leetcode.cn/problems/coin-change-2/

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

动态规划的本质是对状态空间的有序不重复遍历
相当于在以状态为点的图上进行拓扑排序

总结

无论多难的题目，按照提取关键信息、人工模拟、定义状态的步骤来解题
动规与贪心的关系
状态与决策的平衡
决策比较复杂，条件比较多——列表法
滚动数组优化空间
“滚动型”环形DP的处理方法——两次DP
背包
动态规划计数原则——不重不漏（最优化问题只要不漏就可以)

279.完全平方数

https://leetcode.cn/problems/perfect-squares/

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;i-j*j>-1;j++)
            {
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

55.跳跃游戏

https://leetcode.cn/problems/jump-game/

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

45.跳跃游戏Ⅱ

https://leetcode.cn/problems/jump-game-ii/

class Solution {
public:
    int jump(vector<int>& nums) {
        int now = 0;
        int ans = 0;
        while (now < nums.size() - 1) {
            int right = now + nums[now];
            if (right >= nums.size() - 1) return ans + 1;
            int nextRight = right;
            int next = now;
            for(int i = now + 1; i <= right; i++) {
                if(i + nums[i] > nextRight) {
                    nextRight = i + nums[i];
                    next = i;
                }
            }
            now = next;
            ans++;
        }
        return ans;
    }
};

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

动态规划二