一、分析题目
状态表示：
- f[i]：从前 i 个数中挑选，最后一个位置的数必选，此时的最大和。
- g[i]：从前 i 个数中挑选，最后一个位置的数不选，此时的最大和。
状态转移方程：
- f[i] = g[i-1] + arr[i]
- g[i] = max(f[i-1], g[i-1])
初始化：
- f[0] = 0，g[0] = 0
二、代码
1、没看题解之前AC的代码
//一维dp-2个状态 #include <iostream> using namespace std; const int N = 2e5+10; int a[N], f[N], g[N]; int main() { int n; cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<=n; i++) { f[i]=max(f[i-1], g[i-1]+a[i]); g[i]=max(f[i-1], g[i-1]); } cout << max(f[n], g[n]) << endl; return 0; } //一维dp-1个状态 #include <iostream> using namespace std; const int N = 2e5+10; int a[N], dp[N]; int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> a[i]; dp[0]=a[0], dp[1]=max(a[0], a[1]); for(int i=2; i<n; i++) dp[i]=max(dp[i-2]+a[i], dp[i-1]); cout << dp[n-1] << endl; return 0; } //力扣AC代码 //一维dp-2个状态 class Solution { public: int rob(vector<int>& nums) { int n=nums.size(); vector<int> f(n+1); vector<int> g(n+1); for(int i=1; i<=n; i++) { f[i]=max(f[i-1], g[i-1]+nums[i-1]); g[i]=max(f[i-1], g[i-1]); } return max(f[n], g[n]); } }; //一维dp-1个状态 public: int rob(vector<int>& nums) { int n=nums.size(); if(n==1) return nums[0]; vector<int> dp(n); dp[0]=nums[0], dp[1]=max(nums[0], nums[1]); for(int i=2; i<n; i++) dp[i]=max(dp[i-2]+nums[i], dp[i-1]); return dp[n-1]; } };
2、值得学习的代码
#include <iostream> using namespace std; const int N = 2e5 + 10; int n; int arr[N]; int f[N], g[N]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i]; for(int i = 1; i <= n; i++) { f[i] = g[i - 1] + arr[i]; g[i] = max(f[i - 1], g[i - 1]); } cout << max(f[n], g[n]) << endl; return 0; }
三、反思与改进
典型的 “打家劫舍” 系列问题，但我还是没能直接 AC，一直显示数组越界，我找了半天的边界，寻思着也没错，后来再仔细看题，发现数据范围看错了，晕这是什么低级错误！
