GESP 7级客观题｜动态规划优化｜课堂讲解

考试频率：低频。本卷共 2 题。

1. 下面代码段可以求两个字符串 s1 和 s2 的最长公共子串（LCS），下列相关描述不正确的是（ ）。

while (cin >> s1 >> s2){
	memset(dp, 0, sizeof(dp));
	int n1 = strlen(s1), n2 = strlen(s2);
	for (int i = 1; i <= n1; ++i)
		for (int j = 1; j <= n2; ++j)
			if (s1[i - 1] == s2[j - 1])
				dp[i][j] = sp[i - 1][j - 1] + 1;
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	cout << dp[n1][n2] << endl; 
}

{{ select(1) }}

• 代码的时间复杂度为$O(n^2)$
• 代码的空间复杂度为$O(n^2)$
• 空间复杂度已经最优
• 采用了动态规划求解

2. 若某动态规划状态 dp[i] 只依赖 dp[i-1]，将二维或一维数组压缩为少量变量主要优化的是（ ）。

   {{ select(2) }}

• 答案正确性
• 空间复杂度
• 输入规模
• 递归深度