class Solution {
public:
    vector<int>path;
    vector<vector<int>>ans;
    int sum;
    void backtrack(int start,vector<int>&nums,int target){
        //递归出口--收集结果
        if(start == nums.size()){
            if(sum==target){
                ans.push_back(path);   
            }
            return;
        }
        int a[2]={1,-1};
        //单层递归逻辑
        for(int i=0;i<=1;i++){
            path.push_back(a[i]);
            sum+=a[i]*nums[start];
            backtrack(start+1,nums,target);
            sum-=a[i]*nums[start];
            path.pop_back();
        }
    }

    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(0,nums,target);
        return ans.size();
    }
};

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       //本题可类比背包问题
       int sum=0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        //边界条件 绝对值范围超过了sum的绝对值范围则无法得到
        if (abs(target) > abs(sum)) return 0;

       //1确定dp数组下标含义
       vector<vector<int>>dp(nums.size(),vector<int>(2*sum+1,0));
       //2初始化第一行数据
        if (nums[0] == 0) {//为0可加可减
            dp[0][sum] = 2;
        } else {//仅有一种情况，以sum为中心点
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }
       //4遍历顺序
       for(int i=1;i<nums.size();i++){
           for(int j=0;j<2*sum+1;j++){
            //    //3递推公式
                int r = (j+nums[i]>2*sum?0:j+nums[i]);
                int l = (j-nums[i]<0?0:j-nums[i]);
                dp[i][j]=dp[i-1][r]+dp[i-1][l];
           }
       }
       //5打印输出
        for(int i=0;i<nums.size();i++){
           for(int j=0;j<2*sum+1;j++){
               cout<<dp[i][j]<<" ";
           }
           cout<<endl;
       }
       return dp[nums.size()-1][sum+target];
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //1确定dp数组下标及含义：dp[i]表示凑齐i元的种类数
        vector<int>dp(amount+1,0);
        //2初始值：dp[0]=0其他都为0
        dp[0]=1;
        // for(int j=0;j<coins.size();j++){
        //     dp[coins[j]]=1;
        // }
        for(int j=0;j<coins.size();j++){
            for(int i=coins[j];i<=amount;i++){
                //3递推公式：dp[i]+=dp[i-coins[j]]
                dp[i]+=dp[i-coins[j]];
            }
        }
        //4遍历顺序：外层是钱币种类数，内层是种类数（特别注意：如果反过来将会形成排列数）
        //5打印DP数组
        for(int i=0;i<=amount;i++){
            cout<<dp[i]<<" ";
        }
        return dp[amount];
    }
};

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i=0;
        int j=s.size()-1;
        while(i<j){
            swap(s[i],s[j]);
            i++;j--;
        }
        return;
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //顺序不同的序列被视作不同的组合。有序组合--排列问题
        //1确定DP数组下标及含义：dp[i]表示凑齐i的组合数
        vector<int>dp(target+1,0);
        //2初始化Dp数组：dp[0]=1
        dp[0]=1;
        //3建立递推公式：dp[i]+=dp[i-nums[j]]
        for(int j=1;j<=target;j++){
            
            for(int i=0;i<nums.size();i++){
                //C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
                if(j>=nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) 
                    dp[j] += dp[j-nums[i]];
            }
        }
        //4确定遍历顺序：外层--钱币数，内层--nums种类
        //5打印DP数组
        for(int i=0;i<=target;i++){
            cout<<dp[i]<<" ";
        }
        return dp[target];

    }
};

class Solution {
public:
    //1确定dp数组，i表示节点数量为i的二叉搜索树种数
    int numTrees(int n) {
        //2dp数组初始化
        int dp[20]={1};
        //4遍历顺序
        for(int i=0;i<=n;i++){
            for(int j=1;j<=i;j++){
                //3递推公式
                dp[i] += dp[j-1]*dp[i-j];    
            }            
        }
        //5打印dp数组
        for(int i=0;i<=n;i++){
            cout<<dp[i]<<" ";
        }
        return dp[n];        
    }
};

class Solution {
public:
    int numSquares(int n) {
        //0构造平方数组
        int m = sqrt(n);
        vector<int>nums(m);
        for(int i=0;i<m;i++){
            nums[i] = (i+1)*(i+1);
        }
        //1确定dp数组下标及含义：dp[i]凑齐i需要的最少数量
        vector<int>dp(n+1,INT_MAX);
        //2初始化dp数组：dp[0]=0，其他为INT_MAX
        dp[0]=0;
        //3确定状态转移方程：dp[i]=min(dp[i],dp[i-n[j]])
        for(int i=0;i<=n;i++){
            for(int j=0;j<m;j++){
                if(i>=nums[j])dp[i]=min(dp[i],dp[i-nums[j]]+1);
            }
        }
        //4确定遍历顺序：先进行整数的遍历，再进行平方数遍历

        //5打印DP数组
        for(int i=0;i<=n;i++){
            cout<<dp[i]<<" ";
        }
        return dp[n];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //遇上一题的区别：上一题不限次数，本题只能是0,1,2次
        //分析：在dp数组的构造上发生改变，一共是5个状态
        //无操作、第一次买入、第一次卖出、第二次买入、第二次卖出，最终状态是第二次卖出（如果有的话）dp[i][4]
        //因此根据以上五个操作写出递推公式

        //1确定dp数组含义：dp[i][j]表示第i天所获得的最大利润，j=0~4表示5个状态
        vector<vector<int>>dp(prices.size(),vector<int>(5,0));
        //2初始化dp数组
        dp[0][0]=0;
        dp[0][1]=0-prices[0];
        dp[0][2]=0;
        dp[0][3]=0-prices[0];
        dp[0][4]=0;
        //3递推公式（五个状态）
        for(int i=1;i<prices.size();i++){
            dp[i][0]=dp[i-1][0];//不操作
            dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1]);//第一次买入
            dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2]);//第一次卖出
            dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3]);//第一次买入
            dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4]);//第一次卖出
        }
        //4递推遍历顺序
        //5打印dp数组
        for(int i=0;i<prices.size();i++){
            cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<" "<<dp[i][3]<<" "<<dp[i][4]<<endl;
        }
        return dp[prices.size()-1][4];
    }
};

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //1确定dp数组下标含义：dp[i]表示凑齐i元需要最少dp[i]枚硬币
        int size = coins.size();
        vector<int>dp(amount+1,65433);
        //2初始化dp[0]=0
        dp[0]=0;
        for(int i=0;i<=amount;i++){
            //int minNum = 1000;
            for(int j=0;j<size;j++){
                //3递推公式dp[i]=min(MIN,dp[i-coins[j]]+1)
                if(i>=coins[j])dp[i]=min(dp[i-coins[j]]+1,dp[i]);
            }
            //dp[i]=minNum;
        }
        //4确定递归遍历顺序：从小开始遍历i，从小开始遍历j 

        //5打印dp数组
        for(int i=0;i<=amount;i++){
            cout<<dp[i]<<" ";
        }
        if(dp[amount]==65433)return -1;
        return dp[amount];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //分析：构建dp数组：第i天可能持有股票也可能不持有股票
        //最终待求的即为最后一天不持有股票的最大利润即dp[size-1][0]
        //可能来自于当天卖出了股票dp[i-1][1]+prices[i]或是前一天本就不持有股票dp[i-1]

        //1确定dp 数组下标及含义：dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润
        vector<vector<int>>dp(prices.size(),vector<int>(2,0));
        //2初始化dp
        dp[0][0]=0;
        dp[0][1]=0-prices[0];
        //3动态转移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        for(int i=1;i<prices.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        //4遍历顺序
        //5打印dp数组
        for(int i=1;i<prices.size();i++){
            cout << dp[i][0]<<" "<<dp[i][1]<<endl;
        }
        return dp[prices.size()-1][0];
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for (int k = 0; k < nums.size(); k++) {
            sum += nums[k];
        }
        if (sum % 2 != 0)return false;
        int tar = sum / 2;
        //1dp数组含义dp[i]表示凑齐重量为i的最大数值总和
        vector<int>dp(tar + 1, 0);
        //2初始化数组dp=0
        for (int i = 0; i < nums.size(); i++) {
            //4确定遍历顺序：i--0~n-1，j--0~sum/2
            for (int j = tar;j>= nums[i]; j--) {
                //3确定递推公式
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        //5打印dp数组
        for (int i = 0; i <= tar; i++)
            cout << dp[i] << " ";
        return dp[tar]==tar;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //设置一个动态值为第i天前的最小买入
        int minN = prices[0];
        //1设置dp数组表示前i天的最大收益
        vector<int>dp(prices.size(),0);
        //2对dp数组进行初始化
        for(int i=1;i<prices.size();i++){
            minN = min(prices[i],minN);
            dp[i]=max(dp[i-1],prices[i]-minN);
        }
        //3动态转移方程dp[i]=max(dp[i-1],price[i]-min)
        //4dp遍历顺序
        //5打印dp数组
        for(int i=0;i<prices.size();i++){
            cout<<dp[i]<<" ";
        }
        return dp[prices.size()-1];
    }
};

class Solution {
public:
    string reverseWords(string s) {
        string ans = "";
        int i = 0, j = 0;
        vector<string>strs;
        while (i<=s.length()-1) {
            if (s[i] == ' ') {
                i++; j++;
            }
            else if (s[j] == ' ') {
                strs.push_back(s.substr(i, j - i));
                i = j;
            }
            else if (j == s.length() - 1) {
                strs.push_back(s.substr(i, j - i + 1));
                break;
            }
            else {
                j++;
            }
        }
        //倒序
        for (int i = strs.size() - 1; i >= 0; i--) {
            ans += strs[i];
            ans += ' ';
        }
        ans.pop_back();
        return ans;
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        int cur=0;
        while(cur<s.length()){
            int l=0,r=0;
            if(cur+2*k<s.length()){//>2k
                l=cur;
                r=cur+k-1;
            }
            else if(cur+k<s.length()){//k-2k
                l=cur;
                r=cur+k-1;
            }
            else{//<k
                l=cur;
                r=s.length()-1;
                
            }
            while(l<r){
                swap(s[l],s[r]);
                l++;r--;
            }
            cur+=2*k;
        }
        return s;
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //本题遇上一题的区别在于：交易数量是一个待定的值，并且长度可以是0！！！
        //因此在dp数组设置以及遍历得到递推公式需要特别注意
        //边界判定
        if(prices.empty())return 0;
        //1dp数组下标及其含义：dp[i][j],i：0~prices.size()-1,j：0~2k(j为奇数--买入，j为偶数--卖出)
        vector<vector<int>>dp(prices.size(),vector<int>(2*k+1,0));
        //2dp数组初始化：凡是买入就－
        for(int i=0;i<2*k+1;i++){
            if(i%2==1)dp[0][i]-=prices[0];
        }
        //3递推公式，当前状态or前一状态的迁移
        for(int i=1;i<prices.size();i++){
            for(int j=0;j<2*k+1;j++){
                if(j==0)dp[i][j]=dp[i-1][j];
                else if(j%2==1)dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                else if(j%2==0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
            }
        }
        //4遍历顺序
        //5打印dp数组
        for(int i=1;i<prices.size();i++){
            for(int j=0;j<2*k+1;j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        return dp[prices.size()-1][2*k];
    }
};