动态规划

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

DP法

// 使用dp[i] 记录到第i个元素的最大子序列和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int dp[nums.size()] = {0};
        dp[0] = nums[0];
        int res = nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i] = max(nums[i],dp[i-1]+nums[i]);
            res = max(dp[i],res);
        }
        return res;
    }
};

198. 打家劫舍

int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        if(size == 2) return max(nums[0],nums[1]);

        vector<int> dp(size+1,0);
        int max_val = 0;
        dp[0] = nums[0];
        dp[1] = nums[1]>nums[0]?nums[1]:nums[0];

        for(int i=2;i<size;i++){
            dp[i] = max(dp[i-2]+nums[i],dp[i-1]);
            if(dp[i]>max_val) max_val = dp[i];
        }
        return max_val;
    }
// 优化版本
    int rob(vector<int>& nums) {
       int prevMax = 0;
        int currMax = 0;
        for (auto x : nums) {
            int temp = currMax;
            // 之前最大利润+抢当前家 or 不抢当前家，保持最大利润
            currMax = max(prevMax + x, currMax);
            prevMax = temp;
        }
        return currMax;
    }

思路1
直接使用一个三维度的dp数组[m][k][j], 保存第m天，操作k次，是否持有股票的最大利润，然后找最大的
max(dp[m-1][0][0],dp[m-1][1][0],dp[m-1][2][0]);

思路2

dp1[i] = max(dp[i-1], prices[i] - minval) 从前往后遍历，表示第1天到第i天之间的最大利润（通过是否在第i天卖出确认）；
dp2[i] = max(dp[i+1], maxval - prices[i]) 从后往前遍历，表示第i天到最后一天之间的最大利润（通过是否在第i天买进确认）；
res = max(dp1 + dp2)，(dp1 + dp2)[i] 正好表示从第1天到最后一天经过两次交易的最大利润，我们的目标是找到令总利润最大的i。

class Solution {
public:
   int maxProfit(vector<int>& prices) {
        int m = prices.size();
        if(m==0) return 0;
        int dp[m][3][2];
        for(int k=0;k<3;k++) //最多可以完成 两笔 交易
        {   dp[0][k][0] = 0; // 第 1 天 操作 k 次 没有股票，所以初始值为 0
            dp[0][k][1] = - prices[0];  // 第 1 天 操作i 次 有股票， 所以初始值为 - prices[0]
        }

        for (int i=1;i<m;i++){
            dp[i][0][0] = dp[i-1][0][0];
            dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0] - prices[i]);
            dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1] + prices[i] ) ;

            dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0] - prices[i]);
            dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1] + prices[i] ) ;
            dp[i][2][1] = max(dp[i-1][2][1],dp[i-1][2][0] - prices[i] ) ;
        }
        int tmp = max(dp[m-1][0][0],dp[m-1][1][0]);
        tmp = max(tmp,dp[m-1][2][0]);
        return tmp;
    }

    int maxProfit(vector<int>& prices) {
        int m = prices.size();
        if(m<2) return 0;
        int dp1[m] = {0};
        int dp2[m] = {0};
        int minval = prices[0];
        int maxval = prices[m-1];

        for(int i=1;i<m;i++){
            dp1[i] = max(dp1[i-1],prices[i]-minval);
            minval = min(minval,prices[i]);
        }

        for(int i=m-2;i>=0;i--){
            dp2[i] = max(dp2[i+1],maxval-prices[i]);
            maxval = max(maxval,prices[i]);
        }
        int tmp = 0;
        for(int i=0;i<m;i++){
            tmp = max(tmp,dp1[i]+dp2[i]);
        }

        return tmp;
    }

};



public int maxProfit(int[] prices) {
        /** 对于任意一天考虑四个变量: fstBuy: 在该天第一次买入股票可获得的最大收益 fstSell: 在该天第一次卖出股票可获得的最大收益 secBuy: 在该天第二次买入股票可获得的最大收益 secSell: 在该天第二次卖出股票可获得的最大收益 分别对四个变量进行相应的更新, 最后secSell就是最大 收益值(secSell >= fstSell) **/
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int p : prices) {
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy + p); 
        }
        return secSell;
    }
    

322. 零钱兑换

这道题综合性特别强,可以用背包,深度遍历(dfs),广度遍历(bfs)

• 首先,背包的动态规划,就是取与不取的问题,

• 其次是,深度遍历(dfs),

两种方式,一种就是用字典记录深度遍历过程中得到金额i的最小个数
一种是,通过判断条件,减少递归次数

• 最后是,广度遍历(bfs),就是每一次从加上所有硬币,因为是广度遍历,所得到一定是可以用最少硬币达到的

BFS暴力法

class Solution {
public:
    
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        int res = 0;
        pair<int,int> P;
        queue<pair<int,long long>> mq;
        int min_val = 100000;
        unordered_map<long long,int> dp;
        sort(coins.begin(),coins.end());

        for(int i=0;i<coins.size();i++){
            mq.push(make_pair(1,coins[i]));
            dp[coins[i]] = 1;
            if(coins[i] == amount) return 1;
        }

        while(!mq.empty()){
            long long tmp = mq.front().second;
            int index = mq.front().first;
            mq.pop();
            for(int i=0;i<coins.size();i++){
                if(tmp+coins[i]==amount ) return index+1;
                if(tmp+coins[i] < amount && dp.find(tmp+coins[i]) == dp.end()){
                    if(tmp+coins[i]<amount){
                        mq.push(make_pair(index+1,tmp+coins[i]));
                        dp[tmp+coins[i]] = index+1;
                    }
                }
            }
        }
        return -1;
    }
};

// 动态规划法
dp[i]表示金额为i需要最少的零钱个数
对于任意金额 j ,dp[j] = min(dp[j],dp[j-coin]+1),如果j-coin存在的话.

假设 f(n) 代表要凑齐金额为 n 所要用的最少硬币数量，那么有：
f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1
其中 c1 ~ cn 为硬币的所有面额。

int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        int min_val = 100000;

        vector<int> dp(amount+1,10000);
        dp[0] = 0;
        for(int i=1;i<=amount;i++){
            for(auto price:coins){
                if(i-price>=0)
                    dp[i] = min(dp[i-price]+1,dp[i]);
            }
        }
        return dp[amount]!=10000?dp[amount]:-1;
}