打家劫舍(java语言描述(动态规划))
2024-10-18 00:47:51
题目描述:
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
解题思路:
不直接考虑所有房子,假设只有1个房子,最大值一定是第一个房子,如果有两个房子,则取两个的最大值
当有n个房子(3个以上)时,最大值为 max(n-1个房子的最大值 , n-2个房子的最大值+第n个房子)
代码:
import java.util.Scanner; public class djjs {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt();
int[] arr = new int[max]; //房屋金额
int[] dp = new int[max]; //第下标个房屋之前的最大值
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
} dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]); for (int i = 2; i < max; i++) {
dp[i] = dp[i - 1] > dp[i - 2] + arr[i] ? dp[i - 1] : dp[i - 2] + arr[i];
}
//输出每个房屋的金额
for (int i = 0; i < max; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
//输出到每个房屋时的最大值
for (int i = 0; i < max; i++) {
System.out.print(dp[i]+" ");
} } }
最新文章
- 设计模式之结构类模式大PK
- awk应用
- ajx技术解析以及模拟jQuery封装
- 【jquery】:表单返回信息
- 滑动菜单栏(一)开源项目SlidingMenu的使用
- HDU 5596 GTW likes gt 倒推
- UI进阶 数据加密
- oracle 导入导出数据
- TCP参数设置
- 从苹果的appstore谈谈web前端那丝毫的追求
- FreeRTOS数据结构(一)--链表和链表项
- Java IO(三)——字节流
- (最长回文子串 线性DP) 51nod 1088 最长回文子串
- 当我们直接打印定义的对象的时候,隐含的是打印toString()的返回值。
- 使用Anemometer基于pt-query-digest将MySQL慢查询可视化
- 06——react组件的基本定义和使用
- lambda表达式和表达式树(深入理解c#)
- Remove duplicates
- 阅读 DPDK 中文论文两则
- centos 7 sshd 重启 停止 启动
热门文章
- 【LeetCode】868. Binary Gap 解题报告(Python)
- 【剑指Offer】扑克牌顺子 解题报告(Python)
- 1065 - Number Sequence &;&;1070 - Algebraic Problem
- Rectangles(hdu2461)
- python学习第四天:python基础(字符编码和乱码到底咋回事儿)
- Codeforces 450E:Jzzhu and Apples(构造,数学)
- 第五个知识点 复杂性为NP类是什么意思
- Going Deeper with Convolutions (GoogLeNet)
- 3 - 基于ELK的ElasticSearch 7.8.x技术整理 - 高级篇( 偏理论 )
- Centos安装rrdtool的yum源