Steward

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

程式語言 - LeetCode - C - 198. House Robber

---

參考資訊：
https://algo.monster/liteproblems/198
https://www.cnblogs.com/grandyang/p/4383632.html

題目：


解答一：

int max(int a, int b)
{
    return a > b ? a : b;
}
 
int rob(int *nums, int numsSize)
{
    int i = 0;
    int ev = 0;
    int od = 0;
 
    for (i = 0; i < numsSize; i++) {
        if ((i % 2) == 0) {
            ev = max(ev + nums[i], od);
        }
        else {
            od = max(ev, od + nums[i]);
        }
    }
    return max(ev, od);
}

解答二：

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

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

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

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

int rob(int *nums, int numsSize)
{
    int i = 0;
    int *dp = malloc(sizeof(int) * numsSize);

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

    return dfs(nums, dp, 0, numsSize);
}