DP：简单多状态模型

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]);
    }
};

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));
    }
};

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]);
    }
};

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]);
    }
};

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;
    }
};

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];
    }
};

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());//找到最大值的位置
    }
};