20-算法解析及优化拓展

4.4.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：算法有两个for循环，一个双重for循环。如果两个字符串的长度分别是m、n，前两个for循环时间复杂度为O(n)和O(m)，双重for循环时间复杂度为O(nm)，所以总的时间复杂度为O(nm)。

（2）空间复杂度：使用了d[][]数组，空间复杂度为O(n*m)。

2．算法优化拓展

大家可以动手实现构造最优解部分，可以直接倒推，也可以在程序开始使用辅助数组记录来源，然后倒推。

想一想还有没有更好的算法求解呢？