class Solution {
public:
    int numSquares(int n) {
        // dp[j]表示第j等于完全完全平方数的最少数量
        vector<int> dp(n+1,INT_MAX);
        // dp[0] = 0
        dp[0] = 0;
        // 组合问题 顺序无所谓
        // 完全背包 顺序
        for(int j=0;j<=n;j++){
        // 物品是完全平方数
            for(int i=1;i*i<=j;i++){
                dp[j] = min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[n];
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //将单词划分 如果 0-j 和 j-i部分都可以在wordDict中找到
        //那么长度为i的字符串可以由wordDic拼接而成
        //dp[i] 表示长度为i的字符串可以由wordDic拼接而成
        unordered_set<string> set(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1);
        dp[0]=true;
        for(int i=1;i<s.size()+1;i++) {
            for(int j=0;j<i;j++) {//用j去划分成两部分
                string sub = s.substr(j,i-j);//后面部分 s[j: i-1]
                if(set.find(sub)!=set.end()&&dp[j]) {//前面部分 s[0: j]
                    dp[i]=true;
                    break; // dp[i] = true了，i长度的子串已经可以拆成单词了，不需要j继续划分子串了
                }
            }
        }
        return dp[s.size()];
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划 本题与买卖股票的最佳时机II 唯一的区是本题只能买卖两次
        // 且同时只能持有一支股票 递推公式 dp[i][0]
        // 第i天第一次持有股票所得现金(选择最低的持有) dp[i][1]
        // 第i天第一次卖出股票所得现金 dp[i][2]
        // 第i天第二次卖出股票所得现金(选择最低的持有) dp[i][3]
        // 第i天第二次卖出股票所得现金
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        // 初始化 dp[0][0] -= prices[0];dp[0][1] = 0;dp[0][2] -= prices[0];
        // dp[0][3] = 0;
        dp[0][1] -= prices[0];dp[0][3] -= prices[0];
        for (int i = 1; i < prices.size(); i++) {
            // 第一次买入
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            // 第一次卖出: 第一次持有+当前股价
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            // 第二次持有需要卖出第一次
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            // 第二次卖出: 第二次持有+当前股价
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size()-1][4];
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //本题与123. 买卖股票的最佳时机 III 唯一的区别是本题可以k次买入
        //通过123. 买卖股票的最佳时机 III我们已经可以发现一个规律了
        //每次买入所得现金=max(之前买入所得现金,卖出上一次所得现金-当钱股价)
        vector<vector<int>> dp(prices.size(), vector<int>(2*k+1, 0));
        // 初始化 dp[0][1] -= prices[0];dp[0][3] -= prices[0];
        for(int j=1;j<2*k;j+=2) dp[0][j] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            // 第j次买入 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            // 第j次卖出: 第j次持有+当前股价 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            for(int j=1;j<2*k;j+=2) {
                dp[i][j]   = max(dp[i - 1][j ], dp[i - 1][j-1] - prices[i]);
                dp[i][j+1] = max(dp[i - 1][j+ 1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[prices.size()-1][2*k];
    }
};