8.욕심

동적 기획: 한 걸음 한 걸음 선택을 하고 하위 문제의 해답에 의존한다.보통 밑에서 위로 해답을 구하는데, 먼저 비교적 작은 자문제를 구하고, 그 다음에 비교적 큰 자문제를 구한다.
욕심: 매번 국부적인 최우선을 찾아낸다.
122. Best Time to Buy and Sell Stock II
무제한 매입 판매 가능
최우수 서브구조:res+=max(0,prices[i] - prices[i-1))

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

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

수조의 마지막 위치에 도달할 수 있는지 구합니다.

class Solution {
public:
    bool canJump(vector& nums) {
        int reach = 0;
        for (auto i = 0; i != nums.size() && i <= reach; ++i) {
            reach = max(reach, nums[i] + i);
        }
        
        return reach >= nums.size() - 1;
    }
};

45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.

44문항과 비슷하지만 마지막 위치에 도달하는 최소 점프를 요구한다.
국부 최우해: 현재 지점에서 도달할 수 있는 가장 먼 거리를 구하고 이 범위 내에서count는 업데이트하지 않습니다.

class Solution {
public:
    int jump(vector& nums) {
        int reach = 0, count = 0, next = 0;
        for (auto i = 0; i < nums.size() - 1; ++i) {
            reach = max(reach, i + nums[i]);
            if (i == next) {
                count++;
                next = reach;
            }
        }
        return count;
    }
}; 

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

만약 모든gas>=모든cost가 있다면 결과는 존재합니다.그리고 시작점은 잉여유량이 가장 적은 다음이다.
최우수자 구조: total=min(total, total+gas[i]-cost[i]).남은 기름량이 가장 적은 다음 기름을 찾아내라.

int canCompleteCircuit(vector& gas, vector& cost) {
    int n = gas.size();
    int total = 0, subsum = INT_MAX, start = 0;
    for (int i = 0; i < n; ++i) {
        total += (gas[i] - cost[i]);
        if (total < subsum) {
            subsum = total;
            start = i + 1;
        }
    }
    
    return (total >= 0) ? start%n : -1;
}

135. Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

다음 순서로 나누어 진행하다

아이당 설탕 1개로 초기화

뒤로 옮겨다니며 뒷rate가 크면 설탕도 앞것보다 1개

더 많이 나눈다.

뒤에서 앞으로 옮겨다니며 전의rate가 크면 설탕을 나누어 max(현재, 후의+1)

최우수자 구조: 왼쪽이 현재보다 크면 왼쪽+1.오른쪽이 현재보다 크면 오른쪽이 +1입니다.

int candy(vector& ratings) {
    if (ratings.size() <= 1) return ratings.size();
    
    int res = 0;
    vector counts(ratings.size(), 1);
    for (auto i = 0; i < ratings.size() - 1; ++i) {
        if (ratings[i + 1] > ratings[i])
            counts[i + 1] = counts[i] + 1;
    }
    
    for (auto i = ratings.size() - 1; i > 0; --i) {
        if (ratings[i - 1] > ratings[i])
            counts[i - 1] = max(counts[i - 1], counts[i] + 1);
    }
    
    for (auto n:counts) 
        res += n;
    return res;
}