search

youngyangyang04 / leetcode-master-comment

用来做评论区
0 stars 0 forks source link

[Vssue]0516.最长回文子序列.md #134

Open youngyangyang04 opened 2 months ago

youngyangyang04 commented 2 months ago

https://www.programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html

Du1in9 commented 1 month ago 
// 例: s = "cbbd"
i = 2: dp = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
  j = 3: 不满足 'b' == 'd', 则 dp[2][3] = max(1,1) = 1 (回文子串"b"或"d")
i = 1: dp = [[1,0,0,0],[0,1,0,0],[0,0,1,1],[0,0,0,1]]
  j = 2: 满足 'b' == 'b', 则 dp[1][2] = 0+2 = 2 (回文子串"bb")
  j = 3: 不满足 'b' == 'd', 则 dp[1][3] = max(1,2) = 2 (回文子串"bb")
i = 0: dp = [[1,0,0,0],[0,1,2,2],[0,0,1,1],[0,0,0,1]]
  j = 1: 不满足 'c' == 'b', 则 dp[0][1] = max(1,1) = 1 (回文子串"c"或"b")
  j = 2: 不满足 'c' == 'b', 则 dp[0][2] = max(2,0) = 2 (回文子串"bb")
  j = 3: 不满足 'c' == 'd', 则 dp[0][3] = max(1,2) = 2 (回文子串"bb")
Takakee commented 3 weeks ago

这里创建dp数组的时候，为什么是dp[len + 1][len + 1]，亲测dp[len][len]就可以了啊