描述
給出一個(gè)字符串署辉，找到最長的重復(fù)子序列的長度灼舍，并且這兩個(gè)子序列不能在相同位置有同一元素。
比如：在兩個(gè)子序列中的第i個(gè)元素不能在原來的字符串中有相同的下標(biāo)涨薪。
樣例
給出str = abc, 返回 0, 不存在重復(fù)子序列
給出str = aab, 返回 1, 兩個(gè)子序列分別是 a(第一個(gè)) 和 a(第二個(gè)).
注意 b 不能被認(rèn)為是子序列的一部分骑素，因?yàn)樗趦蓚€(gè)子序列里面有相同的下標(biāo)。
給出str = aabb, 返回 2
思路
這是LCS的變種題目刚夺！
其意思是求字符串中兩個(gè)不相交的相等子序列献丑，那么聯(lián)想一下如何求兩個(gè)不同字符串序列中的最長公共子序列（對(duì)于序列的下標(biāo)位置沒有要求）。就可以看出侠姑，這個(gè)題目就是求兩個(gè)相同字符串序列的最長公共子序列创橄，但是有個(gè)要求，就是相同字符的下標(biāo)不能相同莽红，轉(zhuǎn)換一下思路妥畏，題目還是很簡單的邦邦。
代碼
class Solution:
"""
@param str: a string
@return: the length of the longest repeating subsequence
"""
def longestRepeatingSubsequence(self, str):
# write your code here
n = len(str)
dp = [[0 for j in range(n+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
if str[i-1] == str[j-1] and i != j:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[n][n]
題目來源
https://www.lintcode.com/problem/longest-repeating-subsequence/description
