记忆化搜索
该题是滑雪的一维版,建议先完成滑雪
记忆化是对于dfs搜索进行优化,对于搜索的一些结果进行记录,从而避免重复搜索。
记忆化搜索的套路:
- 状态方程,状态方程需要初始化一个没被搜索过的值
- 递归函数,返回动态规划方程的结果
时间复杂度 $O(N)$,空间复杂度$O(N)$
参考文献
算法基础课
AC代码
class Solution {
public:
int dx[2] = {-1, 1};
int n;
vector<int> f;
int dp(vector<int>& ratings, int x) {
if (f[x] != -1) return f[x];
f[x] = 1;
for (int i = 0 ; i < 2 ; i ++) {
int a = x + dx[i];
if (a < 0 || a >= n) continue;
if (ratings[a] < ratings[x])
f[x] = max(f[x], dp(ratings, a) + 1);
}
return f[x];
}
int candy(vector<int>& ratings) {
n = ratings.size();
f = vector<int>(n, -1);
int res = 0;
for (int i = 0 ; i < n ; i ++) {
res += dp(ratings, i);
}
return res;
}
};