Best Time to Buy and Sell Stock II

머리가 굳은건지 DP문제를 계속 풀어도 쏙쏙 와닿지는 않아서 큰일인거 같다. 다만 계속해서 노트에 적다보니깐 뭔가 답을 확인 했을때도 완전히 모르는건 아니고 아쉽네 라고 생각하는 수준까지는 와서 다행이다. 이 문제는 가장 많은 수익을 내야하는 한번에 루프로 DP식 계산을 하며 풀어야한다. 솔직히 DP를 설계하는거까지가 꽤 어려운 수준이지 종이에다가 계속 적다보면은 어떤 중복되는 패턴? 이 보이기도 해서 조금씩 성장한다고 생각한다. 당장 회사에서도 배울게 많아가지고 문제를 많이 풀지는 못하지만 그래도 한시간 씩이라도 계속 하력 노력중이다.

DP 수식을 계속해서 노트에 적다보면은 바로 전에 계산했던 값들이 중복되는데 이것을 DP[i-1] 값으로 잡았고 유일하게 DP가 못잡은 값인 prices[i] - prices[i-1] 을 더해주면서 마지막에는 최고값만 남기게 하면 쉽게 풀 수 있다.

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length]; 
        dp[0] = 0; 
        for(int i = 1; i < prices.length; i++){
            dp[i] = dp[i-1] + Math.max(0,prices[i] - prices[i-1]); 
        }
        return dp[prices.length-1]; 
    }
}