题解 | #打家劫舍(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型
 */
int max(int a,int b)
{
    return a>b?a:b;
}

int rob(int* nums, int numsLen ) {
    // write code here
    if(numsLen==1)
    {
        return nums[0];
    }
    int dp[numsLen+1];
    dp[0]=0;//不偷钱
    dp[1]=nums[0];
    for(int i=2;i<=numsLen;i++)
    {
        dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);
        //动态转移方程考虑的是：偷上一家最多钱dp[i-1]与放弃偷上一家并偷上上家钱的比较dp[i-1]+nums[i-1]
    }
    return dp[numsLen];
}