记忆化搜索和动态规划

记忆化搜索和动态规划常常是两种成对出现的解法。

合唱

这道题来自网易2018校园招聘编程题真题集合的倒数第二题。

记忆化搜索偏重于在传统的递归搜索中复用一些中间结果。其框架大致为result = search(start)形式,并且在能够复用前必定已经到达过一次递归底部。
对于本题,记忆化搜索是简单易懂的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int solve(int i, int j) {
if (dp[i][j] == -1)
{
int next = max(i, j) + 1;
if (next > n)
{
return 0;
}
int ch1 = i == 0 ? solve(next, j) : solve(next, j) + abs(a[next] - a[i]);
int ch2 = j == 0 ? solve(i, next) : solve(i, next) + abs(a[next] - a[j]);
dp[i][j] = min(ch1, ch2);
}
return dp[i][j];
}
int main() {
int T, cas = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
memset(dp, -1, sizeof dp);
printf("%d\n", solve(0, 0));
#ifdef __ACM
system("pause");
#endif
return 0;
}

常可以借助于反向DP来取代记忆化搜索里面的递归。
正向DP的方法容易进入一个误区,这里的dp[i][j]并不一定从dp[i - 1][j]dp[i][j - 1]之间转移得到,例如dp[3][2]完全可以是由dp[3][0]得到的。