一、递归写法（dfs深搜）
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 507;
int home[N],mem[N];
int n;
int dfs(int x)
{
if (x > n) return 0;
return max(dfs(x + 1), dfs(x + 2) + home[x]); //不选/选
}
void solve()
{
memset(home, 0, sizeof(home)); //因为有多组测试样例，所以每一轮都需要初始化操作
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> home[i];
}
int res=dfs(1);
cout << res << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ =1; cin >> _;
while (_--) solve();
system("pause");
return 0;
}
二、记忆化搜索
- 对于已经计算过了的数据不做重复计算，如图中计算了两次店铺4的价值，造成了代码累赘，完全可以用一个记忆化数组mem来存储
- 由于没有return函数直接返回，所以需要用条件判断把语句关联在一起，防止越界
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 507;
int home[N],mem[N];
int n;
int dfs(int x)
{
if (mem[x]) return mem[x]; //记忆化搜索数组
int sum = 0;
if (x > n) sum=0; //注意：由于没有return函数直接返回，所以需要用条件判断把语句关联在一起，防止越界
else sum=max(dfs(x + 1), dfs(x + 2) + home[x]); //不选/选
mem[x] = sum;
return sum;
}
void solve()
{
memset(home, 0, sizeof(home)); //因为有多组测试样例，所以每一轮都需要初始化操作
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> home[i];
}
int res=dfs(1);
cout << res << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ =1; cin >> _;
while (_--) solve();
system("pause");
return 0;
}
三、动态规划（dp）–>倒序
PS:应该于dfs的公式一致
- 由于到递归中，只有归的操作才是产生答案的操作，那么我们是否可以仅仅对归进行操作，从而得出答案呢？–>于是，dp产生了
- 相当于我们从边界往回进行倒序遍历，从已知推未知，所以应该是
for (int i = n; i >= 1; i--) - 注意:p[i]表示从n-i的最大店铺的值，所以应该输出dp[1]
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 507;
int home[N],mem[N],dp[N];
int n;
int dfs(int x)
{
if (mem[x]) return mem[x]; //记忆化搜索数组
int sum = 0;
if (x > n) sum=0; //注意：由于没有return函数直接返回，所以需要用条件判断把语句关联在一起，防止越界
else sum=max(dfs(x + 1), dfs(x + 2) + home[x]); //不选/选
mem[x] = sum;
return sum;
}
void solve()
{
memset(home, 0, sizeof(home)); //因为有多组测试样例，所以每一轮都需要初始化操作
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> home[i];
}
for (int i = n; i >= 1; i--)
{
dp[i] = max(dp[i + 1], dp[i + 2] + home[i]);
}
cout << dp[1]; //表示从n-i的最大店铺的值，所以应该输出dp[1]
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ =1; cin >> _;
while (_--) solve();
system("pause");
return 0;
}
四、动态规划（正序）
- 那么倒序看起来奇奇怪怪的，我们是否可以正序呢？？答案是肯定的，此时我们的搜索方向与原来的恰恰相反，也就是从n开始搜索
- 注意这道题还有一个映射的思想，同时扩大嘿嘿嘿
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 507;
int home[N],mem[N],dp[N];
int n;
int dfs(int x)
{
if (mem[x]) return mem[x]; //记忆化搜索数组
int sum = 0;
if (x > n) sum=0; //注意：由于没有return函数直接返回，所以需要用条件判断把语句关联在一起，防止越界
else sum=max(dfs(x + 1), dfs(x + 2) + home[x]); //不选/选
mem[x] = sum;
return sum;
}
void solve()
{
memset(home, 0, sizeof(home)); //因为有多组测试样例，所以每一轮都需要初始化操作
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> home[i];
}
for (int i = 1; i<=n; i++)
{
//dp[i] = max(dp[i - 1], dp[i - 2] + home[i]);
dp[i+2] = max(dp[i+1], dp[i] + home[i]);
}
cout << dp[n+2]; //表示从1-n的最大店铺的值，所以应该输出dp[n]
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ =1; cin >> _;
while (_--) solve();
system("pause");
return 0;
}
``