题解 | 密码截取

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String password = in.nextLine();
        int n = password.length();
        int[][] dp = new int[n][n];
        int ret = dfs(dp, 0, n - 1, password);
        System.out.println(ret);
    }


    public static int dfs(int[][] dp, int i, int j, String p) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        if (i == j) {
            dp[i][j] = 1;
            return dp[i][j];
        }
        if (i - 1 == j) {
            dp[i][j] = 0;
            return 0;
        }
        if (p.charAt(i) == p.charAt(j)) {
            int l = dfs(dp, i + 1, j - 1, p);
            if (l == j - i - 1) {
                dp[i][j] = l + 2;
            } else {
                dp[i][j] = Math.max(dfs(dp, i + 1, j, p), dfs(dp, i, j - 1, p));
            }
        } else {
            dp[i][j] = Math.max(dfs(dp, i + 1, j, p), dfs(dp, i, j - 1, p));
        }
        return dp[i][j];
    }
}

十分经典的一个题目（经典题目意味着其实就不难哈）

dp[i][j]的定义就是原问题——求password[i,j]中最长的回文子串，而dp[0][n-1]就是原问题的解。具体解答时，这里是采取自顶向下（也就是递归）的方式进行求解的，并使用备忘录的方式来加快计算重复的子问题。在面试coding中，建议也采取这种方式，而不推挤使用两层循环进行迭代的解法，因为这样思路清晰。