【每日一题】LeetCode 213.打家劫舍II - 线性DP

本文最后更新于:2023年11月8日 中午

LeetCode 213.打家劫舍II

思路

这道题有一道前置题目,即LeetCode 198.打家劫舍,这道前置题目没有环形,是一道常规的线性DP,在每一步都分别判定选和不选的状态即可,而到了本题内,因为是环形的,那么在起始点(终点)的地方就要注意一下,这里起点终点相互影响,所以我们要用分支结构控制一下每个分支的计算的房子,防止少判断

C++代码

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
class Solution {
public:
int rob(vector<int>& nums) {
int n=nums.size();
if(n==0) return 0;
if(n==1) return nums[0];
if(n==2) return max(nums[0], nums[1]);

int ans=0, f, g;
f=nums[2]; g=0;
for(int i=3;i<n;i++)
{
int lastf=f,lastg=g;
f=lastg+nums[i];
g=max(lastf, lastg);
}
ans=g+nums[0];

f=nums[1]; g=0;
for(int i=2; i<n;i++)
{
int lastf=f, lastg=g;
f=lastg+nums[i];
g=max(lastf, lastg);
}
ans=max(ans, max(f,g));
return ans;
}
};

AcWing 1055.股票买卖

思路I

这道题在蓝桥杯选拔校赛中出现过,贪心的思路也很简单,判断每天比前一天是涨还是跌就好了,如果明天股票会跌那么今天全部卖掉,如果明天股票涨那么就要大量买入,得到的结果一定是最优的。

C++代码I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>

using namespace std;

const int N=1e5+10;
const int INF=0x3f3f3f;

int n;
int a[N];

int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int res=0;
for(int i=1;i<=n;i++)
if(a[i]-a[i-1]>0) res+=a[i]-a[i-1];
cout<<res<<endl;
return 0;
}

思路II

这道题正解应该使用DP来实现的,分析下来一共有两个状态要推:

  1. 当前处于未持股状态
    对应的转换有买入和不买入两种处理
  2. 当前处于持股状态
    对应的转换状态就有卖出和不卖出
    由此就可以推出状态转移方程。

C++代码II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f;
int n;
int w[N];
int f[N][2];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);

f[0][1] = -INF;
for (int i = 1; i <= n; ++i) {
f[i][0] = max(f[i - 1][0], f[i - 1][1] + w[i]);
f[i][1] = max(f[i - 1][1], f[i - 1][0] - w[i]);
}
printf("%d\n", f[n][0]);
return 0;
}

【每日一题】LeetCode 213.打家劫舍II - 线性DP
https://www.0error.net/2021/04/cdd03afb.html
作者
Jiajun Chen
发布于
2021年4月15日
许可协议