当前位置：网站首页>[动态规划]DP24 打家劫舍(二)-中等

[动态规划]DP24 打家劫舍(二)-中等

2022-07-16 22:28:00 【51CTO】

描述

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

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

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

输入描述：

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

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

输出描述：

输出最多的偷窃金额

示例1

输入：

输出：

说明：

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

示例2

输入：

输出：

说明：

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

题解

动态规划解法

       
       #include <bits/stdc++.h>
       
       int 
       
       solve(
       
       const 
       
       std::vector
       
       <
       
       int
       
       > 
       
       &
       
       v)
       
{
       
       if (
       
       v.
       
       size() 
       
       == 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       if (
       
       v.
       
       size() 
       
       == 
       
       1)
       
  {
       
       return 
       
       v[
       
       0];
       
  }
       
       std::vector
       
       <
       
       int
       
       > 
       
       dp(
       
       v.
       
       size(), 
       
       0);
       
       // 只取头，不取尾
       
       dp[
       
       0] 
       
       = 
       
       v[
       
       0];
       
       dp[
       
       1] 
       
       = 
       
       std::max(
       
       v[
       
       0], 
       
       v[
       
       1]);
       
       for (
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       < 
       
       v.
       
       size() 
       
       - 
       
       1; 
       
       ++
       
       i)
       
  {
       
       dp[
       
       i] 
       
       = 
       
       std::max(
       
       dp[
       
       i 
       
       - 
       
       1], 
       
       dp[
       
       i 
       
       - 
       
       2] 
       
       + 
       
       v[
       
       i]);
       
  }
       
       int 
       
       ans 
       
       = 
       
       dp[
       
       v.
       
       size() 
       
       - 
       
       2];
       
       // 只取尾，不取头
       
       dp[
       
       0] 
       
       = 
       
       0;
       
       dp[
       
       1] 
       
       = 
       
       v[
       
       1];
       
       for (
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       < 
       
       v.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       dp[
       
       i] 
       
       = 
       
       std::max(
       
       dp[
       
       i 
       
       - 
       
       1], 
       
       dp[
       
       i 
       
       - 
       
       2] 
       
       + 
       
       v[
       
       i]);
       
  }
       
       return 
       
       std::max(
       
       ans, 
       
       dp.
       
       back());
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n;
       
       std::cin 
       
       >> 
       
       n;
       
       std::vector
       
       <
       
       int
       
       > 
       
       v(
       
       n);
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       ++
       
       i)
       
  {
       
       std::cin 
       
       >> 
       
       v[
       
       i];
       
  }
       
       std::cout 
       
       << 
       
       solve(
       
       v) 
       
       << 
       
       std::endl;
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.