记忆化搜索和动态规划

发表于 |

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

合唱

这道题来自网易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]得到的。