DAY19-动态规划(二)

今天继续整理几题动态规划～
昨天放的几题都是相对简单的，今天会放几题推演比较复杂或比较多维度的
明天整理状态压缩的题目

例题实战

879. Profitable Schemes

[法一]暴力递回

一开始没有特别好的思路，就先暴力递回..
暴力递回的思路就是基本就是先考虑搜索出每一种组合...
但答案要求的是回传组合总数!
思考组合总数要怎麽计算
考虑一件物品：
(此物品被拿取的组合数)+(此物品被拿取的组合数)
当然，要能够被拿取
再来讨论一下基础状态：考虑第1件物品(下标0)时，若此时minProfit小於等於0时，至少会有一种组合，若此时成员够完成第一项任务，则有两种组合，若此时成员无法完成第一个任务，并且minProfit非小於等於0时
，就是0种组合数
以此种方式及基础往下推演，就是暴力递回的写法

[法二]DP

经由推演可以发现考虑第i个物品时，只与考虑i-1个物品时有关，所以可以写成dp来计算
最後(代码中)还可以进行经典的降维(要计算i只需要i-1)

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        /*由暴力法递回可以发现
        dp[i][j][k] 表示考虑前下标i的任务有j个成员最小利润要k
        dp[i][j][k] = dp[i-1][j-gp[i]][k-pf[i]]+dp[i-1][j][k] {j-gp[i]>0}
        */
        const int mod = 1e9+7;
        int N = profit.size();
        vector<vector<vector<int>>> dp(N, vector<vector<int>>(n+1, vector<int>(minProfit+1, 0)));
        for(int i = 0; i<N; ++i){
            for(int j=0; j<=n; ++j){
                for(int k=0; k<=minProfit; ++k){
                    if(i==0){
                        //已经不需要更多利润，但还可以加入任务
                        
                        //此时可以选或不选 2种
                        if(k==0&&j>=group[0]){
                            dp[0][j][0] = 2;
                        }
                        //不需要利润了但不能加入任务
                        //不选 1种
                        else if(k==0){
                            dp[0][j][0] = 1;
                        }
                        //还需要利润
                        //任务0可以满足利润k
                        else if(j>=group[0]&&profit[0]>=k){
                            dp[i][j][k] = 1;
                        }
                    }
                    else{
                        int pf_needed = k-profit[i];
                        if(pf_needed<0){
                            pf_needed = 0;
                        }
                        if(j-group[i]>=0)
                            dp[i][j][k]+=dp[i-1][j-group[i]][pf_needed]%mod;
                        dp[i][j][k]+=(dp[i-1][j][k]%mod);
                    }
                }
            }
        }
        return dp[N-1][n][minProfit]%mod;
        /*
        选i or 不选i
        dfs(idx-1, n-group[i],minProfit-profit[i])+ 
        dfs(idx-1, n, minProfit)
        */
        //return dfs(profit.size()-1,n,minProfit, group, profit);
    }
    //暴力dfs
    // int dfs(int idx, int n,int minProfit, vector<int>& gp, vector<int>& pf){
    //     int pick_idx = 0;
    //     int not_pick_idx = 0;
    //     if(idx==0){
    //         //already get enough profit
    //         if(minProfit<=0){
    //             if(n>=gp[0]){
    //                 return 2;
    //             }
    //             else{
    //                 return 1;
    //             }
    //         }
    //         else if(pf[0]>=minProfit&&n>=gp[0]){
    //             return 1;
    //         }
    //         else{
    //             return 0;
    //         }
    //     }
    //     else{
    //         //从这个递回可以看出决定现在的答案只跟idx-1有关，所以可以动态规划
    //         if(n-gp[idx]>=0)//有办法完成这项任务
    //             pick_idx = dfs(idx-1, n-gp[idx], minProfit-pf[idx], gp, pf); //pick i
    //         not_pick_idx = dfs(idx-1, n, minProfit, gp, pf);//dont pick i
    //     }
    //     return pick_idx+not_pick_idx;
    // }
};

714. 买卖股票的最佳时机含手续费

这题设定要用动态规划来写..
递回法会超时..
递归法：
但想法是一样的，核心在於每一天可能发生的事有：持有时卖出、不卖出；不持有时买入、不买入
递回的想法就很简单，直接递回传入现在的状态(持有、不持有、持有价值、现在获利)尝试，
动态规划：
用两个数组，存的数值都在於该状态是不持有或持有，则可推导转移方程
{持有[i] = Max(持有[i-1], 不持有[i-1]-价格[i])}
{不持有[i] = Max(不持有[i], 持有[i-1]+价格[i]-手续费)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size()==0){
            return 0;
        }
        vector<int> dp_hand(prices.size(), 0); //hand
        vector<int> dp_sold(prices.size(), 0); //sold
        dp_hand[0] = -prices[0];
        for(int i = 1; i<prices.size(); i++){
            dp_hand[i] = max(dp_hand[i-1], dp_sold[i-1]-prices[i]); //想法：能在第一天买就不要再更贵的第二天买
            dp_sold[i] = max(dp_hand[i-1] + prices[i]-fee, dp_sold[i-1]);
        }
        return dp_sold[dp_sold.size()-1]; // 最大值发生在最後是卖出的情况下(未卖出不可能是最佳解答)
        //return get_profit(prices, 0, 0, 0, fee);
    }
    // int get_profit(const vector<int>& prices, int storage_val, int cur_profit, int date, int fee){
    //     int sell_pro = -1, buy_pro = -1;
    //     if(date>prices.size()-1){
    //         return cur_profit;
    //     }
    //     if(storage_val){
    //         if(prices[date] < storage_val+fee)
    //             return get_profit(prices, storage_val, cur_profit, date+1, fee);
    //         //sell or dont sell
    //         sell_pro = max(get_profit(prices, storage_val, cur_profit, date+1, fee),
    //             get_profit(prices, 0, cur_profit+prices[date], date+1, fee)
    //         );
    //         return sell_pro;
    //     }
    //     else{
    //         //buy or dont buy
    //         buy_pro = max(get_profit(prices, prices[date], cur_profit-prices[date]-fee, date+1, fee), 
    //             get_profit(prices, storage_val, cur_profit, date+1, fee)
    //         );
    //         return buy_pro;
    //     }
    // }
};

停在原地的方案数

推演转移方程
dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1] ~~>注意边界
dp[i][j] 代表从pos = 0开始到位置i的方法数
而dp[i][j]可能从 i. i-1, i+1推演，可得转移方程
初始化的细节在於在arrLen足够下，走到最远的方法数为1(就只能一直走)

class Solution {
public:
    /* dp[pos][steps]  (from pos = 0)
    --> dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1]
    */
    int numWays(int steps, int arrLen){
        int mod = 1000000007;
        arrLen = min(steps, arrLen);
        vector<vector<long>> dp(arrLen, vector<long>(steps+1, 0));
        // initialize
        for(int i = 0;i<arrLen; i++){
            dp[i][0] = 0;
        }
        for(int i = 0; i<=steps&&i<arrLen; i++){
            dp[i][i] = 1;
        }
        for(int j = 1; j<steps+1; j++){
            for(int i = 0; i<arrLen; i++){
                if(i==0)
                    dp[i][j] = (dp[i][j-1]+dp[i+1][j-1])%mod;
                else if(i==arrLen-1)
                    dp[i][j] = (dp[i][j-1]+dp[i-1][j-1])%mod;
                else
                    dp[i][j] = (dp[i-1][j-1]+dp[i+1][j-1]+dp[i][j-1])%mod;
            }
        }
        return dp[0][steps];
    }
};