以前上课时,没认真学习数据结构和算法,虽然之后自己有在学,但总是学到一半就停下了,导致现在算法方面欠缺有点大。这一次求解字符串中的最长回文子串问题,并没有什么好的思路,但也想了一个:找出所有重复的字符,然后查看相同字符间的子字符串是否组成回文子串。
而在这里,使用动态规划则更加优美。不过先得知道什么是动态规划。
动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划背后的思路是把一个给定的问题切分成不同部分(即子问题)再求解,再根据子问题的解以得出原问题的解。在这个问题上,假设 是字符串 的最长回文子串,则 (当不是回文字符串)。求解过程采用自底向上的方法,这样就消除了重复。
在 Lisp 中,判断字符串 是否是回文字符串:
回文字符串中又分两种,长度为奇数和偶数,分开判断代码会有重复,而 Lisp 的宏可以解决这个问题。
接触 Lisp 以来第一次实践中使用宏,挺简单的,但感觉还不错。
领取专属 10元无门槛券
私享最新 技术干货