题解 | #打家劫舍2#

打家劫舍(二)

http://www.nowcoder.com/practice/6a8b2ceb3f8f4e5891939d7d7cbbd2c4

将题目转化为求0-n-1以及1-n的问题(第0个屋子不抢,以及第n个屋子不抢的问题)

import java.util.Scanner;

/**
 * @program: springDemo
 * @author: JiaLe Hu
 * @create: 2022-03-11 10:08
 **/

public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt();

        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = reader.nextInt();
        }

        int[] tmp1 = new int[n - 1];
        int[] tmp2 = new int[n - 1];
        System.arraycopy(p, 0, tmp1, 0, n - 1);
        System.arraycopy(p, 1, tmp2, 0, n - 1);
        System.out.println(Math.max(helper(tmp1), helper(tmp2)));
    }

    public static int helper(int[] p) {
        if (p == null || p.length == 0)
            return 0;
        int n = p.length;
        int[][] dp = new int[n][2];

        // init
        dp[0][0] = 0;
        dp[0][1] = p[0];

        // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
        // dp[i][1] = dp[i - 1][0] + p[i]

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + p[i];
        }

        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}
全部评论

相关推荐

码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
昨天 11:05
门头沟学院 运营
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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