1.贪心理论与常见的证明方法

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX-1);
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                if(coins[j]<=i)
                {
                    dp[i]=min(dp[i-coins[j]]+1,dp[i]);
                }
            }
        }
        dp[amount]=dp[amount]==INT_MAX-1?-1:dp[amount];
        return dp[amount];
    }
};

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        coins[5] = coins[10] = coins[20] = 0;
        for(int bill : bills) {
            coins[bill]++;
            if(!exchange(bill - 5)) return false;
        }
        return true;
    }
private:
    bool exchange(int amount) {
        for(int x : {20, 10, 5}) {
            while (amount >= x && coins[x] > 0) {
                amount -= x;
                coins[x]--;
            }
        }
        return amount == 0;
    }
    unordered_map<int, int> coins;
};

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int candy=0,child=0;
        while(child<g.size() && candy<s.size())
        {
            if(g[child]<=s[candy])
            {
                child++;
            }
            candy++;
        }
        return child;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++){
            ans += max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int now = 0;
        int ans = 0;
        while (now < nums.size() - 1) {
            int right = now + nums[now];
            if (right >= nums.size() - 1) return ans + 1;
            int nextRight = right;
            int next = now;
            for(int i = now + 1; i <= right; i++) {
                if(i + nums[i] > nextRight) {
                    nextRight = i + nums[i];
                    next = i;
                }
            }
            now = next;
            ans++;
        }
        return ans;
    }
};

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(),
            [](const vector<int>& a, const vector<int>& b) {
                return a[0] - a[1] < b[0] - b[1];
            });
        int ans = 0;
        for(int i = tasks.size() - 1; i >= 0; i--) {
            ans = max(tasks[i][1], ans + tasks[i][0]);
        }
        return ans;
    }
};