#yyds干货盘点# 动态规划专题：打家劫舍(二)

村上春种树 lv.2

发布时间：2022-11-08 00:19:04 294

相关标签： # java# spring# java# 数据

1.简述：

描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足，数组中每个值满足

输入描述：

第一行输入一个正整数 n ，表示数组的长度。

第二行输入 n 个正整数，表示每个房间存有的现金。

输出描述：

输出最多的偷窃金额

示例1

输入：

4
1 2 3 4

输出：

说明：

最优方案是偷第 2 4 个房间

示例2

输入：

3
1 3 6

输出：

说明：

由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间

2.代码实现：

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];

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

        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]);
    }
}

文章来源： https://blog.51cto.com/u_15488507/5820708

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。