题目链接 LeetCode 135
错误的代码:
class Solution {
public:
vector<int> f;
vector<int> w;
int n;
int candy(vector<int>& ratings) {
n = ratings.size();
w = ratings;
f.resize(n, -1);
int res = 0;
for (int i = 0; i < n; i ++ ) res += dp(i);
return res;
}
int dp(int x) {
if (f[x] != -1) return f[x];
f[x] = 1;
if (x && w[x - 1] < w[x]) f[x] = max(f[x], dp(x - 1) + 1);
if (x<=w.size()-2&& w[x + 1] < w[x]) f[x] = max(f[x], dp(x + 1) + 1);
return f[x];
}
};
但如果将
if (x<=w.size()-2&& w[x + 1] < w[x]) f[x] = max(f[x], dp(x + 1) + 1);
更改为
if (x <=n-2 && w[x + 1] < w[x]) f[x] = max(f[x], dp(x + 1) + 1);
便可以AC