[数据结构与算法]leetcode198打家劫舍

思路：

1. 动态规划
2. 就是隔一个拿物品

f[n] = max(f[n-1],f[n-2]+nums[i]);

代码

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define max(a,b) ((a)>(b)?a:b)
int rob(int* nums, int numsSize){
    int f[numsSize];
    memset(f,0,sizeof(int)*numsSize);
    f[0] = nums[0];
    if (numsSize==1)
    {
        return f[0];
    }
    f[1] = max(f[0],nums[1]);
    int i=0;
    int max_r = max(f[0],f[1]);
    for(i=2;i<numsSize;i++){
        f[i] = max(f[i-1],f[i-2]+nums[i]);
        max_r = max(f[i],max_r);
    }
    return max_r;
    
}

int main(){
    int nums[] = {1,2,3,1};
    printf("%d\n",rob(nums,4));
}