Leetcode - 746. Min Cost Climbing Stairs

문제

각 계단을 오르는 비용을 나타내는 배열이 주어진다. 계단은 1칸 혹은 2칸씩 오를 수 있다. 최소의 비용으로 꼭데기 까지 오른다면 얼마가 드는가?

Input: cost = [10,15,20]
Output: 15

해결 : DP O(N)

r(n) = min(재귀(n-1), 재귀(n-2))

형식의 min/max 를 구하는 재귀 + DP 문제.

cost 배열이 [10, 15, 20] 이렇게 주어졌을때 점화식이 dp[n] = cost[n] + min(dp[n-1], dp[n-2]) 이라면, cost[3] 는 존재하지 않기 때문에 재귀함수 내에서 접근하면 런타임에러가 발생한다. 이런 경우는 애초에 리턴값계산에 재귀함수를 두 번 호출하는게 좋다. return min(recur(n-1), recur(n-2))

1. Constraints
 - the stair start from left to right? -> yes
 - the cost value 0 <= cost[i] <= 999
 - 2 <= cost.length <= 1000
2. Ideas
 - DP
   dp[n] = cost[n] + min(dp[n-1], dp[n-2])
3. Test Cases
 - min lenth input
 - 
4. Coding

#define min(a, b)   (((a) < (b)) ? (a) : (b))
int target;
int recur(int *c, int *dp, int n)
{
    if (dp[n])
        return dp[n];
    
    /* base case */
    if (n == 0)
        return c[0];
    if (n == 1)
        return c[1];
    
    /* recursion */
    dp[n] = c[n] + min(recur(c, dp, n - 1), recur(c, dp, n - 2));
    return dp[n];
}

int minCostClimbingStairs(int* cost, int costSize){
    int dp[1000] = {0}; 
    return min(recur(cost, dp, costSize - 1), recur(cost, dp, costSize - 2));
}