一、打家劫舍（1）
. - 力扣（LeetCode）
class Solution {
public:
int rob(vector<int>& nums)
{
int n=nums.size();
vector<int> f(n);
auto g=f;
f[0]=nums[0];
for(int i=1;i<n;++i)
{
f[i]=g[i-1]+nums[i];
g[i]=max(f[i-1],g[i-1]);
}
return max(g[n-1],f[n-1]);
}
};二、打家劫舍（2）
. - 力扣（LeetCode）
class Solution {
public:
int rob1(vector<int>& nums,int left,int right)
{
if(left>right) return 0;
int n=nums.size();
vector<int> f(n);
auto g=f;
f[left]=nums[left];
for(int i=left+1;i<=right;++i)
{
f[i]=g[i-1]+nums[i];
g[i]=max(f[i-1],g[i-1]);
}
return max(g[right],f[right]);
}
int rob(vector<int>& nums)
{
int n=nums.size();
return max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
}
};三、删除并获得点数
. - 力扣（LeetCode）
class Solution {
public:
int deleteAndEarn(vector<int>& nums)
{
//转化为打家劫舍问题 首先要先找到数组中的最大值，然后用这个最大值去创建数组
int Max=*max_element(nums.begin(),nums.end());
vector<int> all(Max+1);//数组模拟哈希表 注意映射关系！
for(int e:nums) all[e]+=e;
//打家劫舍的数组创建完成
int n=all.size();
vector<int> f(n);
auto g=f; //不用初始化，因为都是0
for(int i=1;i<n;++i)
{
f[i]=g[i-1]+all[i];
g[i]=max(f[i-1],g[i-1]);
}
return max(g[n-1],f[n-1]);
}
};四、粉刷房子
. - 力扣（LeetCode）
class Solution {
public:
int minCost(vector<vector<int>>& costs)
{
int n=costs.size();
vector<vector<int>> dp(n+1,vector<int>(3));
//创建虚拟节点要注意下标的映射关系 以及虚拟节点的填值不影响最终结果
for(int i=1;i<=n;++i)
{
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];
}
return min(min(dp[n][0],dp[n][1]),dp[n][2]);
}
};五、买卖股票的最佳时机（1）
. - 力扣（LeetCode）
该题并不是用dp去做的，只是为了保证股票类型题目的齐全
思路：我们要找到最大的数和最小的数，并且保证最小的数是在最大数的左边 ，所以不能直接用找大和找小的思路，用maxi更新最大利润，用mini记录最小的股票。
class Solution {
public:
int maxProfit(vector<int>& prices)
{
int mini=INT_MAX;
int maxi=0;
for(int price:prices)
{
//遍历的时候，我们随时去更新最小的值，然后让每一位数都来-最小值 更新利润，这里不能直接用最大值
//因为最大值可能在最小值的左边
maxi=max(maxi,price-mini);
mini=min(price,mini);
}
return maxi;
}
};六、买卖股票的最佳时机（2）
. - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& prices)
{
//有两种状态，第i天结束处于买入状态（手上有股票，可卖） 第i天结束后处于交易状态（手上没有股票，可以买
int n=prices.size();
//创建两个dp表
vector<int> f(n);//第i天结束后处于买入状态
//情况1，前一天处于买入状态，啥也没干，还是处于买入状态f[i]=f[i-1]
//情况2，前一天卖过，然后今天刚买 f[i]=g[i-1]-prices[i]
auto g=f;//第i天结束后处于交易状态
//情况1，前一天还是可交易状态，啥也没干 g[i]=g[i-1]
//情况2.前一天处于买入状态，今天刚卖出一只股票，外加手续费 g[i]=f[i-1]+prices[i]-fee
//初始化，
f[0]=-prices[0];
for(int i=1;i<n;++i)
{
f[i]=max(f[i-1],g[i-1]-prices[i]);
g[i]=max(g[i-1],f[i-1]+prices[i]);
}
return g[n-1];
}
};七、买卖股票的最佳时机（3）
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& nums) {
//buy1表示当天结束有一支股票在手 sell1表示刚卖了一次，没股票
//buy2表示卖了一次又买了一次 有股票 sell2表示两次都卖了
int n=nums.size();
int buy1=-nums[0],sell1=0,buy2=-nums[0],sell2=0;
for(int i=1;i<n;++i)
{
buy1=max(buy1,-nums[i]); //要么就是没做 要么就是今天刚买
sell1=max(sell1,buy1+nums[i]);
buy2=max(buy2,sell1-nums[i]);
sell2=max(sell2,buy2+nums[i]);
}
return sell2;
}
};八、买卖股票的最佳时机（4）
. - 力扣（LeetCode）
class Solution {
public:
int maxProfit(int k, vector<int>& prices)
{
const int inf=0x3f3f3f3f;//INT_MAX/2
int n=prices.size();
k=min(k,n/2);
//该题涉及到3个维度，一个是价格，一个是交易次数，一个是当前的状态（2种）
//所以我们根据当前的情况去分成两个二维数组，分别对应的一种状态，然后一个维度是价格，一个维度是交易次数
//f表示第i天处于买入状态（有股票），g表示第i天出去卖出状态（没股票）
vector<vector<int>> f(n,vector<int>(k+1,-inf));
auto g=f;
f[0][0]=-prices[0];
g[0][0]=0;
for(int i=1;i<n;++i)
{
for(int j=0;j<=k;++j)
{
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
//代码优化，因为有可能当前的状态
g[i][j]=g[i-1][j];
if(j>=1) g[i][j]=max(g[i][j],f[i-1][j-1]+prices[i]);
}
}
// int ret=0;
//最后最大值肯定是没有股票的情况
//for(int i=0;i<=k;++i)//在g[i]的最后一行去找最大的交易
// ret=max(ret,g[n-1][i]);//因为不同的交易次数都可能会得到不一样的结果
//对于一个递减的数列来说，交易0次的结果更优
return *max_element(g[n-1].begin(),g[n-1].end());//找到最大值的位置
}
};九、买卖股票的最佳时机含冷冻期
. - 力扣（LeetCode）
class Solution {
public:
int maxProfit(vector<int>& nums) {
//一共有3个状态 dp[i][0]表示第i天结束手里有股票
//dp[i][1]表示第i天结束后 手里没有股票，且可交易
//dp[i][2]表示第i天结束后处在冷冻期（手里没有股票，且不可交易）
int n=nums.size();
vector<vector<int>> dp(n,vector<int>(3));
dp[0][0]=-nums[0];
for(int i=1;i<n;++i)
{
//可能什么也没做dp[i-1][0] 也可能前一天没股票，今天刚买
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-nums[i]);
//要么就是什么都没干 要么就是前一天处于冷冻期
dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
//只有可能是前一天有股票 今天刚卖
dp[i][2]= dp[i][0]+nums[i];
}
return max(dp[n-1][1],dp[n-1][2]);
}
};
十、多状态dp的简单总结
1、通过买卖股票3可以发现，其实对于一些可以直接枚举出情况的动态规划，我们就不一定需要去创建一个dp数组，而是直接根据枚举的几种方式创建变量去模拟，这样更高效
2、通过买卖股票4我们可以发现，我们对dp数组不存在的状态设计虚拟节点这个思路还可以是从动态转移方程上入手，用条件判断去规避不存在的状态
3、通过买卖股票的最佳时机含冷冻期可以发现，要认真的思考当前状态下，前一个状态可能是什么样的，通过今天进入新状态时又是怎么样的
4、虚拟节点设置的时候，如果我们设计最大值和最小值，可能会存在越界的风险，所以我们可以用0x3f3f3f3f来初始化比较保险
5、学会去在动态规划以外的地方去做优化
