《Leetcode》动态规划-求不相邻数的最大和
题目
已知一个数组a[n]，不能取相邻的数，求最大的和
，其中数组有正有负，且无序
a={1,-3,4,5,7,8}
int maxGain(vector a)
{
}
解析
这种类型动态规划题，一般先暴力递归，找到直接的思路，后优化成dp表，最后优化成普通的循环。难点在于找边界条件和转移公式。
方法一：递归暴力求解
#include <vector>
#include <algorithm>
using namespace std;
int process(vector<int>& a, int i)
{
if (i == 0)
{
if (a[i] < 0)
return 0;
else
return a[0];
}
else if (1 == i)
{
if (a[0] <= 0 && a[1] <= 0)
return 0;
else
return max(a[0], a[1]);
}
int m = max(process(a, i - 2) + a[i], process(a, i - 2));
int n = process(a, i - 1);
return max(m, n);
}
int maxGain(vector<int> a)
{
if (a.empty()) return 0;
int N = a.size();
return process(a, N-1);
}
int main()
{
vector<int> a{
1,-2,4,5,7,8 };
auto res = maxGain(a);
return 0;
}
输出结果：
res: 14
此题注意边界条件，如果第一个第二个连续为负值，递归时不做判断的话就会出错。
如果输入改为vector a{ -1,-2,4,5,7,8 }，则结果为13
输出结果：
res: 13
方法二：基于暴力递归优化成缓存表
// aaa111.cpp: 定义应用程序的入口点。
//
#include "aaa111.h"
#include <vector>
#include <algorithm>
using namespace std;
//方法一：暴力递归
int process(vector<int>& a, int i)
{
if (i == 0)
{
if (a[i] < 0)
return 0;
else
return a[0];
}
else if (1 == i)
{
if (a[0] <= 0 && a[1] <= 0)
return 0;
else
return max(max(a[0], a[1]),a[0]+a[1]);
}
int m = max(process(a, i - 2) + a[i], process(a, i - 2));
int n = process(a, i - 1);
return max(m, n);
}
//方法一：缓存表
int process2(vector<int>& a, int i, vector<int>& dp)
{
if (i < 0) return 0;
if (dp[i] != 0) return dp[i];
//非边界条件
int m = max(process2(a, i - 2,dp) + a[i], process2(a, i - 2, dp));
int n = process2(a, i - 1, dp);
dp[i] = max(m, n);
return dp[i];
}
int maxGain(vector<int> a)
{
if (a.empty()) return 0;
int N = a.size();
return process(a, N-1);
}
int maxGain2(vector<int> a)
{
if (a.empty()) return 0;
int N = a.size();
if (N == 2) return max(max(a[0], a[1]), a[0] + a[1]);
vector<int> dp(N + 1, 0);
//边界条件
//if (0 == i)
{
if (a[0] < 0)
dp[0] = 0;
else
dp[0] = a[0];
}
//if (1 == i)
{
if (a[0] <= 0 && a[1] <= 0)
dp[1] = 0;
else
dp[1] = max(max(a[0], a[1]), a[0] + a[1]);
}
return process2(a, N - 1, dp);
}
int main()
{
vector<int> a{
1,-2,4,5,7,8 };
auto res = maxGain(a);
auto res1 = maxGain2(a);
std::cout << "res: " << res << std::endl;
std::cout << "res1: " << res1 << std::endl;
return 0;
}
方法三：基于缓存表优化成非递归方式
这个也简单，自己写吧
