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

打家劫舍(一)

http://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    //动态规划的解法
    //定义一个同样大小的dp数组,其含义位dp[i]的含义为从第0家偷到第i家时能偷到的最大财产为dp[i]这么大
    //假设当前来到某一家时,小偷可以选择偷这一家也可以选择不偷,如果选择偷,那么dp[i]=dp[i-2]+arr[i],
    //如果不偷这一家那么dp[i]=dp[i-1].
    //dp数组的初始化为d[0]=arr[0],dp[1]=max{arr[0],arr[1]};
    public int rob (int[] nums) {
        // write code here
        if(nums.length<=0)
            return 0;
        //考虑到nums数组的特殊情况,如果nums数组只有一个值,那直接返回这个值即可
        if(nums.length==1)
            return nums[0];
        int []dp=new int[nums.length];//申请一个dp数组
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);//初始化完成
        for(int i=2;i<dp.length;i++){
            //当前来到第i家有两种选择,偷或者不偷,取这两个决策下的最大收益
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[dp.length-1];//返回最大值
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:06
点赞 评论 收藏
分享
宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
06-04 09:27
门头沟学院 Java
点赞 评论 收藏
分享
昨天 13:48
门头沟学院 C++
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务