LeetCode 가 주식 을 매매 하 는 가장 좋 은 시기 (동태 계획)

목차
 
간단 한 소개
분석 하 다.
총결산
간단 한 소개
leetcode 에는 주식 매매 에 관 한 동적 계획 문제 가 몇 개 있다.다음은 이런 문제 의 모델 을 살 펴 보 자.
배열 을 지정 합 니 다. 그 i 번 째 요 소 는 주어진 주식 이 i 일 째 가격 입 니 다.
당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.당신 은 최대 k 건의 거래 를 완성 할 수 있 습 니 다.
주의: 너 는 여러 건의 거래 에 동시에 참여 할 수 없다.여기 서 말 하 는 K 건 거래 는 한 번 의 매입 과 한 번 의 판매!!
 
분석 하 다.
우 리 는 3 차원 DP 로 이 문 제 를 기록 하여 해결 할 수 있다.
dp [i] [k] [0] = max (dp [i - 1] [k] [0], dp [i - 1] [k] [1] + a [i]) / / 판매 시 횟수 가 변 하지 않 음
dp [i] [k] [1] = max (dp [i - 1] [k] [1], dp [i - 1] [0] - a [i]) / / 매입 시 횟수 - 1 여 기 는 우리 의 약속 이 고, 사실 반대로 도 가능 합 니 다 (매도 시 - 1 횟수)
첫째 날
2 차원: 현재 최대 k 회 거래
3 차원: 현재 주식 보유 여부 1: 보유, 0: 보유 하지 않 음
 
전달 식 은 이해 하기 쉽 지만 K 값 은 분류 하여 토론 해 야 합 니 다.
해법 1: K 가 무한대 일 때, 즉 무한 거래 가 가능 할 때.무한 거래 를 할 때 우 리 는 욕심 을 생각해 서 해결 할 수 있다. 분명히 좋 은 것 을 보면 받 는 것 이 가장 좋 은 결 과 를 얻 을 수 있다.
해법 2: 위의 전달 식 령 k = 1 을 얻 을 수 있 습 니 다.
    dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i]);     dp[i][1] = max(dp[i-1][1],dp[i-1][0] - a[i]);
 
122. 주식 매매 의 적기 II

class Solution {
public:
    int maxProfit(vector& a) {
        
        int n = a.size();
        int ans = 0;
        for(int i = 1;i a[i-1])ans += a[i] - a[i-1];//           
            
        }
        return ans;
    }
};



class Solution {
public:

    // dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i]);
    // dp[i][1] = max(dp[i-1][1],dp[i-1][0] - a[i]);

    int maxProfit(vector& a) {
        
        int n = a.size();
        if(!n)return 0;
        int dp_1,dp_0;
        for(int i = 0;i

 
그래서 원래 문제 의 풀이 방향:
k > = n / 2 는 우리 가 무한 거래 를 할 수 있다 고 생각 할 수 있 고 상기 욕심 의 방식 을 사용 할 수 있다.
k < n / 2, 상기 동적 계획 방향 을 사용 합 니 다.
188. 주식 매매 의 적기 IV

class Solution {
public:
    int maxProfit(int k, vector &prices) {
        if (prices.empty()) return 0;
        if (k >= prices.size()/2) return solveMaxProfit(prices);//    
        int n = prices.size();
        vector > > dp(n,vector< vector >(k+1,vector(2,0)));
        
        for(int i = 0;i &prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};

 
 
총결산
leetcode 이 문제 의 변종 은 여러 가지 가 있다.
1 회 만 거래 가능: 최저점 매입, 최저점 매도 가능
수수료 포함: 위의 배달 식 에 추가 요금 을 더 하면 됩 니 다.
나 는 먼저 위의 두 문 제 를 써 야만 이 문제 의 본질 을 똑똑히 볼 수 있다 고 생각한다.