【golang必备算法】动态规划 Letecode 516.最长回文子序列
2021/9/14 20:34:58
本文主要是介绍【golang必备算法】动态规划 Letecode 516.最长回文子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
516.最长回文子序列
题目
![2021-09-14 19-40-58 的屏幕截图](/upload/202109/14/202109142034545757.png)
思路
回文子序列都是动态规划经典题目,用从Carl哥那里学来的动态规划五部曲:
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 列举推导dp数组
确定dp数组以及下标的含义
dp[i] [j]
:字符串s在[i, j]
范围内最长的回文子序列的长度为dp[i] [j]
.
确定递推公式
如果s[i]与s[j]相同,那么dp[i] [j]
= dp[i + 1] [j - 1] + 2
;
如果s[i]与s[j]不相同,说明s[i]
和s[j]
的同时加入 并不能增加[i,j]区间回文子串的长度,那么分别加入s[i]
、s[j]
看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1] [j]
。
加入s[i]的回文子序列长度为dp[i] [j - 1]
。
那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1] [j], dp[i] [j - 1])
;
dp数组如何初始化
这里我们使dp[i][j]=1
也就是当i与j相同,一个字符的回文子序列长度就是1。
确定遍历顺序
注意我们二维数组dp[i][j]
的定义,如果i>j
是没有意义的。
![2021-09-14 18-48-20 的屏幕截图](/upload/202109/14/202109142034578589.png)
从上面图中可以看出如果我们想求dp[i][j]
,那么其他3个必须都是已知的,很明显从上往下遍历是不行的,我们只能让i从最后一个字符往前遍历,j从i的下一个开始遍历,也就是从下到上,从左到右
的顺序,这样才能保证计算d
的时候,a,b,c
的值都已经计算过了。
列举推导dp数组![1628749934-fuNRFa-image](/upload/202109/14/202109142034580317.png)
列举完毕后,发现dp[0][length - 1]
即是最后需要的结果返回即可。
代码
func longestPalindromeSubseq(s string) int { l:=len(s) dp:=make([][]int,l) for i:=0;i<l;i++{ dp[i]=make([]int,l) } for i:=0;i<l;i++{ for j:=0;j<l;j++{ if i==j{ dp[i][j]=1 }else{ dp[i][j]=0 } } } for i:=l-1;i>=0;i--{ for j:=i+1;j<l;j++{ if s[i]==s[j]{ dp[i][j]=dp[i+1][j-1]+2 }else{ dp[i][j]=max(dp[i+1][j],dp[i][j-1]) } } } return dp[0][l-1] } func max(a,b int)int{ if a>b{ return a } return b }
这篇关于【golang必备算法】动态规划 Letecode 516.最长回文子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26解决google chrome helper 内存占用较高!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb