[DP - 1D, Easy] Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=leetcode-75

돌다리 건너기인가.. 비슷한 문제를 본 것 같은데
DP 초급에 많이 등장하는 유형인 듯

메모이제이션 사용해서 바로 풀어봤다.
중요한 부분은 한 칸 또는 두 칸을 뛰어서 끝낼 수도 있다는 점이다.
그러므로 dp배열의 마지막과 그 전 칸에서 작은 값을 리턴해야 맞다.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];

        for (int i=0; i<n; i++) {
            dp[i] = cost[i];
        }

        for (int i=2; i<n; i++) {
            dp[i] += Math.min(dp[i-1], dp[i-2]);
        }
        return Math.min(dp[n-1], dp[n-2]);
    }
}

근데 이거 생각해보면 처음에 dp배열을 전부 초기화할 필요 없었다.
어차피 i=2부터 돌거라면 해당 for문 안에서
dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]) 해서 초기화와 누계 덧셈을 같이 해도 되는거다.
LeetCode 테스트케이스 상 런타임에는 아무런 차이를 보이지 않음, 어차피 O(n)이라서 그런가

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];

        dp[0] = cost[0];
        dp[1] = cost[1];

        for (int i=2; i<n; i++) {
            dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
        }
        return Math.min(dp[n-1], dp[n-2]);
    }
}

다른 방법으로... 이것도 전 문제처럼 공간최적화가 가능할 듯 싶다.
배열도 사용하지 않고 갱신할 변수만 두면 똑같은 논리로 해결 가능하긴 하다.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        
        int prev1 = cost[0];
        int prev2 = cost[1];

        for (int i=2; i<n; i++) {
            int current = cost[i] + Math.min(prev1, prev2);
            prev1 = prev2;
            prev2 = current;
        }
        return Math.min(prev1, prev2);
    }
}