2021年下半年软件设计师下午真题答案及解析（四）

生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。具体来说，编辑距离是指将一个字符串变换为另一个字符串所需要的最小操作次数。操作有三种，分别为：插入一个字符、删除一个字符以及将一个字符修改为另一个字符。用字符数组str1和str2分别表示长度分别为len1和len2的字符串，定义二维数组d记录求解编辑距离的子问题最优解，则该二维数组可以递归定义为：

【C代码】
下面是算法的C语言实现。

• 常量和变量说明
  A，B：两个字符数组
  d：二维数组
  i，j：循环变量
  temp：临时变量
• C程序

#include 
#define N 100
char A[N]="CTGA";
char B[N]="ACGCTA";
int d[N][N];
int min(int a, int b) {
	return a <b ? a: b;
}
int editdistance(char *str1, int len1, char *str2, int len2) {
	int i, j;
	int diff;
	int temp;
	for(i=0; i<=len1; i++) {
		d[i][0]=i;
	}
	for(j=0; j<=len2; j++)	{
		(1);
	}
	for(i=1;i<=len1;i++)	{
		for(j=1; j<=len2; j++)	{
			if((2)) {
				d[i][j]=d[i-1][j-1];
			}else {
				temp=min(d[i-1][j]+1, d[i][j-1]+1);
				d[i][j]=min(temp, (3));
			}
		}
	}
	return (4);
}
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

【问题1】(8分)
根据说明和C代码，填充C代码中的空(1)~(4)。
【问题2】(4分)
根据说明和C代码，算法采用了(5)设计策略，时间复杂度为(6)(用O符号表示，两个字符串的长度分别用m和n表示)。
【问题3】(3分)
已知两个字符串A="CTGA"和B=“ACGCTA”，根据说明和C代码，可得出这两个字符串的编辑距离为(7)。
参考答案：
问题1：
(1) d[0][j]=j
(2) str1[i-1]==str2[j-1]
(3) d[i-1][j-1] +1
(4) d[len1][len2]
问题2：
（5）动态规划法 （6）O(mn)
问题3：
（7）4
答案解析：

动态规划法离不开一个关键词，拆分 ，就是把求解的问题分解成若干个子阶段，前一问题的结果就是求解后一问题的子结构。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

适用性
适用动态规划的问题必须满足最优化原理和无后效性。

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

解题思路

1. 确定最优子结构:比如我们要求的结果F(X)的最优子结构可能为F(X-1)和F(X-2）

2. 列转移方程:根据最优子结构可以列出转移方程F(X)=F(X-1)+F(X-2)

3. 确定边界值:确定问题的边界，即当F(n)有可以确定的具体的值

时间复杂度

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

常见的时间复杂度量级有：

常数阶O(1)
对数阶O(logN)
线性阶O(n)
线性对数阶O(nlogN)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2^n)

动态规划算法一般是n步叠代计算局部最优解，每一步叠代需要计算m个子项，那么时间复杂度就是O(m*n)。如果只保存一步叠代的结果，空间复杂度就是O(m)；如果需要保存k步叠代结果，空间复杂度就是O(m*k)