【动态规划】【记忆化搜索】CODEVS 3409 搬运礼物 CodeVS原创

考虑暴力递归求解的情况：

f(i)=min(a(i),f(i-1),f(i-2),...,f(1))

由于只要参数相同，f()函数的返回值是一样的，因此导致了大量的重复计算，所以我们可以记忆下来。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int n,a[5001],memory[5001];
 6 int f(int cur)
 7 {
 8     if(memory[cur]!=-1) return memory[cur];
 9     int res=a[cur];
10     for(int i=1;i<cur;i++)
11       res=min(res,a[cur-i]+f(i));
12     return memory[cur]=res;
13 }
14 int main()
15 {
16     scanf("%d",&n);
17     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
18     memset(memory,-1,sizeof(memory));
19     memory[1]=a[1];
20     printf("%d
",f(n));
21     return 0;
22 }