老师您好，请问最小编辑距离的算法可以用栈实现么？我看目前大部分是用动态方法实现的

Answer 1

liuyubobobo 2017-09-07 00:56:30

最小编辑距离本身就是一个很标准的动态规划问题有成熟的状态定义和状态转移方程。动态规划问题都可以转换成记忆化搜索。记忆化搜索都是用递归实现。递归算法都可以转化为非递归算法。递归转非递归的算法都用栈实现。但是本质解决问题的算法思想还是动态规划。栈只是一个数据结构不是一种算法思想。

所以我没有特别理解你的问题。你是认为动态规划实现有什么缺点还是你有更好的利用栈解决这个问题的思路

• 提问者 qq_阿凡提cpp_0 #1

  非常感谢！

• 提问者 qq_阿凡提cpp_0 #2

  我用栈结构和递归的方法实现了一个，但是显然没有用动态规划的方法有效。。。我也是听别人说用栈比数据结构要更有效