Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 746. Min Cost Climbing Stairs

---

參考資訊：
https://www.cnblogs.com/grandyang/p/8343874.html

題目：


解答一：

int min(int a, int b)
{
    return a > b ? b : a;
}
 
int minCostClimbingStairs(int *cost, int costSize)
{
    int i = 0;
    int c0 = 0;
    int c1 = 0;
 
    for (i = 0; i < costSize; i++) {
        int t = min(c0, c1) + cost[i];
 
        c0 = c1;
        c1 = t;
    }
 
    return min(c0, c1);
}

解答二：

int min(int a, int b)
{
    return a > b ? b : a;
}

int dfs(int *cost, int *dp, int step, int max_step)
{
    if (step >= max_step) {
        return 0;
    }

    if (dp[step] != -1) {
        return dp[step];
    }

    dp[step] = cost[step] + min(dfs(cost, dp, step + 1, max_step), dfs(cost, dp, step + 2, max_step));
    return dp[step];
}

int minCostClimbingStairs(int *cost, int costSize)
{
    int i = 0;
    int *dp = malloc(sizeof(int) * costSize);

    for (i = 0; i < costSize; i++) {
        dp[i] = -1;
    }

    return min(dfs(cost, dp, 0, costSize), dfs(cost, dp, 1, costSize));
}