C++每日一练:打家劫室(详解动态规划法)

这篇具有很好参考价值的文章主要介绍了C++每日一练:打家劫室(详解动态规划法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。
C++每日一练:打家劫室(详解动态规划法)


提示:以下是本篇文章正文内容,下面案例可供参考

一、题目

题目名称:
打家劫舍

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

输入描述:
输入一个正整数n代表房屋的数量(n≤100),接着输入n个非负整数代表每间房屋的现金数量

输出描述:
小偷能偷取的最大金额。

示例1
输入
4
1 2 3 1

输出
4

二、分析

我们假设只有三个房间,事情就很简单了。做为专业小偷,我们知道,房屋编号是从0开始的,只能偷1号房屋或0号+2号房屋。为了取得最大战果,我们分别去看了看每个房屋能偷到多少。出门比较一下,就知道结果了。
我们逛完了三个房屋,现在站在第2号房屋门口来思考一下,就是选择0和2,或选1的问题。
我们把0+2能偷到的钱先记在2号房屋门上,把1号能偷到的钱记在1号门上,然后去看看3号房屋有多少钱可偷。这样1、2、3号房屋又成了一个同样的选择…
我们不停的在门上记录能偷到的钱,不停的用同样的方法选择。
拿示例来说,我们在1号房屋门上记上2毛,2号房屋门上记上4毛(0号加2号),然后和3号房屋来比较,显然4毛大于1号的2毛加3号的1毛。侦察完成,就偷0号加2号了!
再找个长点的例子:
1 2 3 2 9 1 2
同样先在1号房屋门上记上2毛,2号房屋门上记4毛(0号+2号),侦察完3号房屋后,就成了:
2 4 2 9 1 2
继续侦察下一家:
4 4 9 1 2
4 (13) 1 2
(13) 5 2
5 (15)
(15)
最后偷得15毛!

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, std::vector<int>& vec){
    int result=0;
    // TODO:
    vector<int> tmp={vec[0], max(vec[0], vec[1])};
    if(n==1) return tmp[0];
    if(n==2) return tmp[1];
    for (int i=2; i<n; ++i){
        tmp[i] = max(tmp[i-1], tmp[i-2]+vec[i]);
    }
    result = tmp[n-1];
    return result;
}

int main() {

    int n;
    std::vector<int> vec;

    std::cin>>n;
    
    std::string line_0, token_0;
    getline(std::cin >> std::ws,line_0);
    std::stringstream tokens_0(line_0);
    while(std::getline(tokens_0, token_0, ' ')){
        vec.push_back(std::stoi(token_0));
    }
    

    int result = solution(n,vec);

    std::cout<<result<<std::endl;

    return 0;

max(vec[0], vec[1])这一句解决了前二个房屋的选择,因为第二个房屋我们必须选前两个中最大的。如果0号是最大的,就把1号变成0号一样,再来继续选择。
举例来看:
7 1 1 2
侦察前二个房屋后就是:
7 7 1 2
然后7 8 2
最后9
如果是这样的:
1 7 2 1
侦察前二个后就还是:
1 7 2 1
所以初始化的时候一定要考虑清楚!

总结

所谓动态规划:就是将问题划分为一系列子问题,求各子问题的最优解,然后以自底向上的方式递归地从子问题的最优解构造出整个问题的最优解。
在本例中,我们把n个房屋不停的当作三个房屋来处理。所以我们设计了一个tmp数组来存储过程数据。
动态规划和分治法有点像,都是把复杂问题分解成简单的小问题。
不过动态规划的子问题之间不是独立的,子问题的解往往会在下一个选择中被使用。
而分治法,一般会把一个复杂的问题分解成若干个独立的子问题,求解子问题后再合成本问题的解。今天的 “小艺照镜子” (本专栏的另一篇文章有详解)就是用分治法解的。文章来源地址https://www.toymoban.com/news/detail-431638.html

到了这里,关于C++每日一练:打家劫室(详解动态规划法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每日一题之打家劫舍

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

    2024年02月08日
    浏览(44)
  • 每日一题之打家劫舍II

    题目链接 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报

    2024年02月08日
    浏览(42)
  • 动态规划_打家劫舍(Ⅰ~Ⅲ)

    打家劫舍系列 返回最大金额 不能同时取相邻两个数 数组数据全部非负 ①dp数组含义 dp[i]表示前i个数中按规则取出的最大总和 ②递推公式 dp[i]=max(dp[i-1],dp[i-2]+nums[i]) 当前最优可以从两个状态推出(前提是前面已经为最优解): 1° 前一个数未取:则当前数取了,则总和最大

    2024年02月03日
    浏览(40)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年01月20日
    浏览(44)
  • 【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心

    打家劫舍 IV【LC2560】 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额

    2024年02月07日
    浏览(43)
  • 力扣198. 打家劫舍(java 动态规划)

    Problem: 198. 打家劫舍 1.构建多阶段决策模型:n个房屋对应n个阶段,每一个阶段决定一个房间是偷还是不偷,两种决策:偷、不偷 2.定义状态:不能记录每个阶段决策完之后,小偷可偷的最大金额,需要记录不同决策对应的最大金额,也就是:这个房屋偷-对应的最大金额;这

    2024年01月21日
    浏览(54)
  • 【学会动态规划】打家劫舍 II(12)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:213. 打家劫舍 II - 力扣(Lee

    2024年02月15日
    浏览(40)
  • leetcode-打家劫舍专题系列(动态规划)

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

    2024年04月14日
    浏览(45)
  • 【LeetCode热题100】198. 打家劫舍(动态规划)

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

    2024年04月11日
    浏览(46)
  • 动态规划-经典dp(打家劫舍,股票等)

    1.1.1 爬楼梯  由于求的是组合数,我们将不同路径相加即可 dp定义: dp[i]为爬到第i阶楼梯的方法数; 转移方程: 初始化:  由于涉及到i-2和i-1,那么我们要从i=2开始遍历,因此要初始化dp[0] = 0,dp[1] = 1(根据定义) 遍历顺序: 从左往右  完整代码:  1.1.2 使用最小花费爬楼梯

    2024年01月19日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包