动态规划二三事<一>
这是对动态规划的一些学习。
这篇主要是最简单的DP和股票问题。
走起~
LeetCode70 爬楼梯：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
这道题有个小问题，我一开始想用递归解决（如下），但是递归这种方法效率并不高，时间复杂度高达O(2^n)，多半要超过时间限制。
class Solution {public:int climbStairs(int n) {if(n<1) return 0;if(n==1) return 1;else if(n==2) return 2;return climbStairs(n-1)+climbStairs(n-2);}};
用DP循环解决：
class Solution {public:int climbStairs(int n) {if(n<=1) return n;int *dp=new int [n+1];dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}};
（偏一下题）再仔细观察发现是斐波那契模样的数列，利用其性质空间复杂度下降到O(1)：
public class Solution {public int climbStairs(int n) {if (n == 1) {return 1;}int first = 1;int second = 2;for (int i = 3; i <= n; i++) {int third = first + second;first = second;second = third;}return second;}}
LeetCode53 最大子序和：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
一般DP：时间复杂度O(N),空间复杂度O(N)
class Solution {public:int maxSubArray(vector<int>& nums) {int size=nums.size(),res=nums[0];vector<int> dp(size);dp[0]=nums[0];//dp[i]用于记录nums[i]结尾的最大子串和for(int i=1;i<size;i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);res=max(dp[i],res);}return res;}};
股票问题（方法来自labuladong）：
定义dp：dp记录状态：dp[天数i][交易数k][是否持有股票0或1]
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
即：前一天没持有股票，这一天不进行操作，故还是没持有；
前一天持有股票，这一天进行操作，故今天就不持有股票，这个dp是前一天现金加上今天卖出股票获得的现金；
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
即：前一天持有股票，这一天不进行操作，故还是持有；
前一天不持有股票，这一天进行操作，故今天就持有股票，这个dp是前一天现金减去今天买入股票支付的现金；
总结方程：
Base Case：
不持有股票现金为0：dp[i][0][0]=0
一开始持有股票为不可能情况，用无穷小值表示：dp[i][0][1]=INT_MIN
状态转移：
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
LeetCode 121 买卖股票的最佳时机：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
由于只进行一次买卖，所以k可去掉。虽然这种方法在这道题目里面效率并不高，但是简单粗暴是不错的。
class Solution {public:int maxProfit(vector<int>& prices) {if(prices.empty()) return 0;int size=prices.size();vector<vector<int> > dp(size,vector<int>(2));dp[0][1]=-prices[0];for(int i=1;i<size;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=max(dp[i-1][1],-prices[i]);}return dp[size-1][0];}};
把数组优化掉。
class Solution {public:int maxProfit(vector<int>& prices) {int n=prices.size();int dp_i_0=0,dp_i_1=INT_MIN;for(int i=0;i<n;i++){dp_i_0=max(dp_i_0,dp_i_1+prices[i]);dp_i_1=max(dp_i_1,-prices[i]);}return dp_i_0;}};
LeetCode 309 最佳买卖时机含冷冻期：
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
与上一题一样，再增加一个变量保存上一次操作后剩的现金。
class Solution {public:int maxProfit(vector<int>& prices) {int n=prices.size();int dp_i_0=0,dp_i_1=INT_MIN;int dp_pre_0=0;for(int i=0;i<n;i++){int t=dp_i_0;dp_i_0=max(dp_i_0,dp_i_1+prices[i]);dp_i_1=max(dp_i_1,dp_pre_0-prices[i]);dp_pre_0=t;}return dp_i_0;}};
LeetCode 714 最佳买卖时机含手续费：
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
万变不离其宗，干就是了：
class Solution {public:int maxProfit(vector<int>& prices, int fee) {int dp_i_0=0,dp_i_1=-50005,n=prices.size();for(int i=0;i<n;i++){dp_i_0=max(dp_i_0,dp_i_1+prices[i]-fee);dp_i_1=max(dp_i_1,dp_i_0-prices[i]);}return dp_i_0;}};
LeetCode 714 最佳买卖最佳时机（k=2）：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
加入k状态（就是多一个维度）
class Solution {public:int maxProfit(vector<int>& prices) {if(prices.empty()) return 0;int n=prices.size();vector<vector<vector<int> > > dp(n, vector<vector<int> >(3, vector<int>(2)));for(int i=0;i<n;i++){for(int k=1;k<=2;k++){if(i-1==-1){dp[i][k][0]=0;dp[i][k][1]=-prices[i];continue;}dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);}}return dp[n-1][2][0];}};
LeetCode 188 最佳买卖最佳时机（k任意值）：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
做的时候遇到好多bug，最要命的是有一个k=1000000的数据，刚开始的报错都没看懂。最后最主要的问题在于：如果k>n/2,那么k就会有多余的。做了很多不必要的计算。
class Solution {public:int maxProfit_lnf(vector<int>& prices) {int n=prices.size();int dp_i_0=0,dp_i_1=INT_MIN;for(int i=0;i<n;i++){int t=dp_i_0;dp_i_0=max(dp_i_0,dp_i_1+prices[i]);dp_i_1=max(dp_i_1,t-prices[i]);}return dp_i_0;}int maxProfit(int k, vector<int>& prices) {if(prices.empty()) return 0;int n=prices.size();if(k>n/2){return maxProfit_lnf(prices);}k=min(k,n/2);vector<vector<vector<int> > > dp(n, vector<vector<int> >(k+1, vector<int>(2)));for(int i=0;i<n;i++){for(int t=1;t<=k;t++){if(i-1==-1){dp[i][t][0]=0;dp[i][t][1]=-prices[i];continue;}dp[i][t][0]=max(dp[i-1][t][0],dp[i-1][t][1]+prices[i]);dp[i][t][1]=max(dp[i-1][t][1],dp[i-1][t-1][0]-prices[i]);}}return dp[n-1][k][0];}};
这次暂时策到这里，虽然是学习心得。。。但写下来还是好累。。。
图片授权：www.unsplash.com
长按二维码关注，共同精进！