最近在leetcode上面做题，有一道算法题是求最长回文序列的。Longest Palindromic Substring。
这题我没有做出来，我的思路是最笨的解法，用一个map来存放每个字母出现的所有索引，然后for循环遍历字符串，当字符在map中取出来不为空，就循环遍历取出来的索引集合到当前索引之间满足回文序列的最大值。例如ababac,当遍历到第3个a时，map中a对应的list值为[0,2],找当前索引4到0之间的最大回文序列长，4到2之间的最大回文序列长。时间复杂度O(n^3)，短点的例子还能跑出结果，要是一大长串跑起来很慢。然后我看了一下别人的答案，根据dp(dynamic programming)进行解答的，时间复杂度是O(n^2)。
dp(i, j) represents whether s(i … j) can form a palindromic substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 … j-1) is a palindromic substring. When we found a palindrome, check if it’s the longest one. Time complexity O(n^2).
大概意思就是用一个boolean的二维数组表示第i到j直接的字符串是否满足回文序列,如果满足，dp[i][j]赋值为true。
按照这个理论，我们可以先判断i+1到j-1之间的字符串是否满足回文序列，如果满足dp[i+1][j-1]=true，然后我们如果有第i,j的字符相等，那么dp[i][j]也是true。
递推关系式,用P(i,j)表示i->j是否是回文序列
P(i, j) = (P(i+1, j-1) and S(i) == S(j))
P(i,i+1) = (P(i,i) and S(i) == S(i+1))
拿ababac来说，先判断P(5,5)=c=true，P(4,4) = a = true，P(4,5) = (P(4,4) and a == c) = false
实现代码如下:
public String longestPalindrome(String s) {
int n = s.length();
String res = null;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
}
if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
我大概理解了其中的意思，但是对动态规化算法还是有点模糊，于是我去搜了一下，看到有篇文章以最少硬币数为例作为DP的入门，我觉得讲的很好，我根据他的讲解也用代码实现了。
例子是这样的，我们有面值1,3,5元的硬币，问凑够N元最少需要几枚硬币。
- 用d(i) = j表示凑够i元需要j枚硬币
- 先看看基础表示，d(0) = 0, d(1) = d(1-1) + 1 这里的1表示1个1元硬币， d(2) = d(2-1) + 1 = 2 这里的1表示1个1元硬币
- d(3) 有2种表示，一个是d(3-1) + 1 这里的1表示1个1元硬币,一个是 d(3-0) + 1 这里的1表示1个3元硬币,显然后者为最优解
- 总结 d(i) = min(d(i-v) + 1) v表示后面1代表的硬币面值
代码实现:用一维数组dp来存放面值i所需要的最小硬币数
public int minCoinNum(int value) {
int[] dp = new int[value + 1];
int[] val = {1, 3, 5};
for (int i = 0; i < dp.length; i++) {
if (i == 0) { //凑齐0面值需要0个硬币
dp[i] = 0;
continue;
}
int min = dp[i - 1] + 1;
for (int v : val) { //遍历所有可能，取最小值
if (i - v >= 0) {
min = Math.min(min, dp[i - v] + 1);
}
}
dp[i] = min;
}
return dp[value];
}