動態規劃求解最長不重疊子串

普通演算法

遍歷所有的不重疊子串，記錄下最大的值

代碼略

動態規劃優化

動態規劃思想的高明之處在於儘可能的使用之前的計算結果，並得出遞推關係，以O(n)的速度完成

假設要計算的字元串為s，使用數組dp保存中間狀態，dp[i]的含義是s的子串s[0..i]末尾的不重疊子串的長度，這樣dp[i]的值就能根據dp[i-1]的值推出，遞推關係如下：

如果s[i]沒有在s[0..i-1]末尾的不重疊子串里出現過，則`dp[i] = dp[i-1] + 1`；

否則`dp[i] = i - li[s[i]]`，其中li[s[i]]表示在s[0..i-1]末尾的不重疊子串里的字元s[i]在字元串s里的索引

只要在計算dp[i]的過程中，找出最大的值，便是最長不重疊子串的長度

那麼，怎樣判斷s[i]有沒有在s[0..i-1]末尾的不重疊子串里出現過呢？

• 使用一個表li(last index)來保存已經遍歷過的字元最後的索引，沒有遍歷過的字元索引為-1

• 使用一個變數ls(last start index)來保存s[0..i-1]末尾的不重疊子串的起始索引

• 只要li[si] >= ls，便可知當前字元s[i]在s[0..i-1]末尾的不重疊子串里出現過

參考代碼

int lengthOfLongestSubstring(string s) { int li[256]; // Last index of s[i] appeared for (int i = 0; i < 256; i++) li[i] = -1; int size = s.size(); if (!size) return 0; // dp[i] is length of substring without repeat character in the end of s[0..i] int *dp = (int *)alloca(size * sizeof(int)); dp[0] = 1; li[s[0]] = 0; int max = dp[0], // Length of Longest substring ls = 0; // Last index of substring represented by dp[i] for (int i = 1; i < size; i++) { int &n = li[s[i]]; // Last index of current character appeared if (n < ls) // Current character is not appeared in the last string dp[i] = dp[i - 1] + 1; else // Appeared dp[i] = i - n, ls = n; n = i; // update index of current character if (dp[i] > max) max = dp[i]; } return max;}

優化空間效率

因為只需要最後的結果，所以可以不使用dp數組保存所有的中間結果，

只需要一個變數 ll(last length) 來保存維持遞推關係的中間結果

代碼略，將上述代碼中的dp[]全部換成 ll 即可

推薦閱讀：