首页
学习
活动
专区
工具
TVP
发布

动态规划与宏

以前上课时,没认真学习数据结构和算法,虽然之后自己有在学,但总是学到一半就停下了,导致现在算法方面欠缺有点大。这一次求解字符串中的最长回文子串问题,并没有什么好的思路,但也想了一个:找出所有重复的字符,然后查看相同字符间的子字符串是否组成回文子串。

而在这里,使用动态规划则更加优美。不过先得知道什么是动态规划。

动态规划(英语:Dynamic programming,简称 DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划背后的思路是把一个给定的问题切分成不同部分(即子问题)再求解,再根据子问题的解以得出原问题的解。在这个问题上,假设 是字符串 的最长回文子串,则 (当不是回文字符串)。求解过程采用自底向上的方法,这样就消除了重复。

在 Lisp 中,判断字符串 是否是回文字符串:

回文字符串中又分两种,长度为奇数和偶数,分开判断代码会有重复,而 Lisp 的宏可以解决这个问题。

接触 Lisp 以来第一次实践中使用宏,挺简单的,但感觉还不错。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180705G1KJR900?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券