Я пытался решить Эта проблема от codechef и создал нисходящее DP-решение, которое использует запоминание. Ниже приведен код для этой проблемы:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
vector<int> height;
vector<int> memo;
int jump(int i)
{
if(memo[i] != -1)
return memo[i];
else
{
int min = 987654321, res;
for(int j = (i - 1);j >= 0;j--)
{
if(!(height[i]-height[j] == 0) && !(height[i]-height[j] & (height[i]-height[j] - 1)))
{
res = jump(j) + height[i]-height[j];
if(res < min)
min= res;
}
}
memo[i] = min;
return min;
}
}
int main(void)
{
int n;
scanf("%d", &n);
height.resize(n, 0);
memo.resize(n, -1);
memo[0] = 0;
for(int i = 0;i < n;i++)
{
scanf("%d", &height[i]);
}
int ans = jump(n-1);
printf("%d\n", ans);
}
Ограничение по времени для этой проблемы составляет 1 секунду, и я увидел, что несколько решений делают почти одно и то же (int снизу вверх DP) и проходят … Но я читал, что восходящий DP и нисходящий DP точно одинаковы в с точки зрения сложности времени, а иногда, в некоторых случаях, лучше. Но, похоже, это нарушает закон …
Я чувствую, что не запоминаю решения правильно и, или, неэффективно определяю подзадачи. Может ли кто-нибудь помочь мне здесь?
Задача ещё не решена.