算法学习010-打家劫舍 c++动态规划算法实现中小学算法思维学习信奥算法解析

C++打家劫舍

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、运行结果

五、考点分析

六、推荐资料

C++打家劫舍

一、题目要求

1、编程实现

你是⼀个专业的⼩偷，计划偷窃沿街的商铺。每间商铺都藏有⼀定的现⾦，影响你偷窃的唯⼀制约因素就是相邻的商铺装有相互连通的防盗系统，如果两间相邻的商铺在同⼀晚上被⼩偷闯⼊，系统会⾃动报警。

给定⼀个代表每个商铺存放⾦额的⾮负整数数组，计算你不触动警报装置的情况下，⼀夜之内能够偷窃到的最⾼⾦额。

2、输入输出

输入描述：第一行输入沿街商铺的个数n（1<=n<=100）

第二行输入n个数

输出描述：只有一行，一个整数，即一夜只能够偷窃到的最高金额

输入样例：

10
5 7 3 6 4 5 9 8 13 11

输出样例：

二、算法分析

从给定题目的初步分析可以看出，针对每一个商铺都有两种情况
一种是偷，另一种就是不偷
而当前商铺是否偷取决于前一个商铺和前两个商铺是否被偷
如果前一个商铺被偷，那当前商铺就不能偷
如果前一个商铺没有被偷，那当前商铺就可以偷
所以可以采用动态规划的方式实现
设置动态数组dp[i]，i表示第几个商铺；dp[i]就是表示包括第i个商铺在内的能偷到的最大金币
经上面分析第i个商铺能偷到的最大金币分成上面两种情况，偷或者不偷
所以可以得出对应的动态数组dp[i]的状态转移方为：dp[i]=max(dp[i-1],dp[i-2]+g[i-2])
数组g用来存储每间商铺能偷到的金币
从动态转移方程我们也可以看出后面的值都由前一个和前两个来决定，所以需要初始化dp数组的第1个和第2个值：dp[1]=g[1]，dp[2]=max(g[1],g[2)；即第一间商铺能偷到的最大值就是第一间商铺的金币，前两间商铺能能偷到的最大金币就是第一间和第二间商铺里面最大的值

三、程序编写

//程序中的dp和cost数组可以使用动态数组vector进行实现更好
#include<bits/stdc++.h>
using namespace std;
int dp[102];			//dp数组表示第i个商品能偷到的最大金额
int rob(int *g,int n)
{dp[1] = g[1];dp[2] = max(g[1],g[2]);for(int i=3;i<=n;i++)//当前商铺分两种情况偷和不偷,如果不偷那就是到第前一商铺偷的最大金币//如果偷那就是到第前二商品偷的最大金币加上当前商铺的金币dp[i] = max(dp[i-1],dp[i-2]+g[i]);return dp[n];
}
int main()
{int n,g[102];cin >> n;memset(g,0,sizeof(g));for(int i=1;i<=n;i++)cin >> g[i];cout << rob(g,n);return 0;
}

本文作者：小兔子编程作者首页：小兔子编程-CSDN博客