文档章节

动态规划:LC198.打家劫舍

曦鱼violet
 曦鱼violet
发布于 07/13 01:47
字数 429
阅读 44
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

题目描述:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

思路:
第i间房可以有两种偷法:只偷i-1房间的;偷i-2房的+当前房间的。
注意代码有点绕的地方在于:dp[i]->nums[i-1], 所以当前房间的金额是nums[i-1]

代码:

class Solution {
    public int rob(int[] nums) {
        //状态数组:dp[i]--第i间房的最大金额
        //方程:dp[i]=max(dp[i-2]+nums[i]××,dp[i-1])
        //                应该是  nums[i-1] 因为i从0开始计数
        //初始值:dp[0]=0; dp[1]=nums[0]
        int len=nums.length;
        if(len<1) return 0;
        int[] dp=new int[len+1];
        dp[0]=0;
        dp[1]=nums[0];
        //i代表的是房间数!i=0没有房子啊
        //dp[0]=nums[0];
        //dp[1]=Math.max(nums[0],nums[1]);

        for(int i=2;i<=len;i++){
            dp[i]=Math.max(dp[i-2]+nums[i-1],dp[i-1]);
        }
        return dp[len];
    }
}
曦鱼violet
粉丝 0
博文 107
码字总数 43783
作品 0
武汉
私信 提问
加载中
请先登录后再评论。
搞定编程大赛必知哪10个算法?

再没有比算法更让人头疼的东西了吧! 前两天参加了一个编程大赛http://www.ijiami.cn/newsInfo?id=519&v=2,有感于算法,所以整理了这篇关于编程竞赛的10个算法。 动态规划(DP)似乎占据了大...

小开2014
2014/10/22
396
6
R语言中文分词 --jiebaR

"结巴"中文分词的R语言版本,支持最大概率法(Maximum Probability),隐式马尔科夫模型(Hidden Markov Model),索引模型(QuerySegment),混合模型(MixSegment),共四种分词模式,同时...

yestr
2014/11/04
7.7K
1
注重提升集合类处理操作的脚本语言--tinyscript

许多的人使用Java来作为主要的编程语言,许多的时候感觉代码太过繁复,当然有Scala、Kotlin、Python等等语言号称可以解决此问题,但是毕竟生态圈的切换不是个小问题。同时语法结构和Java相去...

悠悠然然
2017/09/01
901
1
Python中文分词组件 - jieba

jieba "结巴"中文分词:做最好的Python中文分词组件 "Jieba" Feature 支持三种分词模式: 精确模式,试图将句子最精确地切开,适合文本分析; 全模式,把句子中所有的可以成词的词语都扫描出...

fxsjy
2012/10/03
16.1W
9

没有更多内容

加载失败,请刷新页面

加载更多

Model S被18轮重卡撞烂 乘客在车辆保护下幸存

日前,国外一位名为quarm813的网友在社交媒体分享了“Model S救他和女儿性命”的经历。 据该用户描述,当地时间7月31日,他驾驶Model S在高速公路快车道上行驶时,一辆18轮重卡突然实线并线闯...

osc_fipgtxy8
30分钟前
7
0
Redis-cluster5.x集群搭建

1.下载redis5.0.2 wget http://download.redis.io/releases/redis-5.0.2.tar.gz #官网下载 tar xzf redis-5.0.2.tar.gz #解压cd redis-5.0.2 yum install gcc #需要gcc来编......

osc_zzg7fpke
32分钟前
11
0
CGB2004-京淘项目Day12

1.还原系统配置 1.1 释放Linux资源 1.1.1 停止数据库主从服务 1.1.2 关闭数据库服务 说明:关闭数据库服务器. 1.1.3 关闭tomcat/mycat服务器 1.1.4关闭nginx服务器 1.2 修改代码中的配置 1.2....

osc_3361hjxk
32分钟前
16
0
【北京迅为】初识i.MX6ULL终结者开发板

目录 一、 开发板初体验 1. 初识i.MX6ULL终结者开发板 一、 开发板初体验 i.MX6ULL终结者开发板是北京迅为电子推出的一款Cortex-A7架构的开发板。采用核心板+底板的方式,如下图所示: 经典蓝...

osc_0esgtdby
33分钟前
8
0
如何利用基于PXI的下一代ATE系统测试平台进行军事/航天/卫星电子设备测试

前言 自动测试设备(ATE)系统用于在生产产品或产品使用过程中测试电子组件,子组件或完整系统的功能和性能,以确保他们可操作性。对设备、电路板、子组件或系统的测试要求从简单到复杂,设计...

osc_mxz6aybo
34分钟前
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部