[左神面试指南] 递归和动态规划[上]篇

CD183 斐波那契数列问题的递归和动态规划1

/*
 * 矩阵快速幂
 * [f(n), f(n-1)] = [1, 1] x [[1, 1], [1, 0]]^(n-2)
 */
public class CD183_1
{
    public static long solution(long n)
    {
        if (n < 1) return -1;
        if (n <= 2) return 1;
        long[][] base = new long[][]{{1, 1}, {1, 0}};
        long[][] res = matrixQuick(base, n - 2);
        return (res[0][0] + res[1][0]) % (long) (1E9 + 7);
    }

    public static long[][] matrixQuick(long[][] base, long l)
    {
        long[][] ans = new long[][]{{1, 0}, {0, 1}};
        while (l != 0)
        {
            if ((l & 1) == 1)
                ans = matrixMul(ans, base);
            base = matrixMul(base, base);
            l >>= 1;
        }
        return ans;
    }

    public static long[][] matrixMul(long[][] ans, long[][] base)
    {
        long MOD = (long) (1E9 + 7);
        long[][] res = new long[2][2];
        for (int i = 0; i < ans.length; i++)
            for (int j = 0; j < base[0].length; j++)
                for (int k = 0; k < ans[0].length; k++)
                    res[i][j] = (res[i][j] + ((ans[i][k] % MOD) * (base[k][j] % MOD)) % MOD) % MOD;
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long N;
        N = in.nextLong();
        System.out.println(solution(N));
    }
}

CD184 斐波那契数列问题的递归和动态规划2

/*
 * 矩阵快速幂
 * [f(n-1), f(n)] = [1, 2] x [[0, 1], [1, 1]]^(n-2)
 */
public class CD184_1
{
    public static long solution(long n)
    {
        if (n < 0) return -1;
        if (n <= 2) return n;
        long[][] base = new long[][]{{0, 1}, {1, 1}};
        long[][] res = matrixQuick(base, n - 2);
        return (res[0][1] + 2 * res[1][1]) % (long) (1E9 + 7);
    }

    public static long[][] matrixQuick(long[][] base, long l)
    {
        long[][] ans = new long[][]{{1, 0}, {0, 1}};
        while (l != 0)
        {
            if ((l & 1) == 1)
                ans = matrixMul(ans, base);
            base = matrixMul(base, base);
            l >>= 1;
        }
        return ans;
    }

    public static long[][] matrixMul(long[][] ans, long[][] base)
    {
        long MOD = (long) (1E9 + 7);
        long[][] res = new long[ans.length][base[0].length];
        for (int i = 0; i < ans.length; i++)
            for (int j = 0; j < base[0].length; j++)
                for (int k = 0; k < ans[0].length; k++)
                    res[i][j] = (res[i][j] + ((ans[i][k] % MOD) * (base[k][j] % MOD)) % MOD) % MOD;
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long N;
        N = in.nextLong();
        System.out.println(solution(N));
    }
}

CD185 斐波那契数列问题的递归和动态规划3

/*
 * 矩阵快速幂
 * [f(n-2), f(n-1), f(n)] = [1, 2, 3] x [[0, 0, 1], [1, 0, 0], [0, 1, 1]]^(n-3)
 */
public class CD185_1
{
    public static long solution(long n)
    {
        if (n < 0) return -1;
        if (n <= 3) return n;
        long[][] base = new long[][]{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}};
        long[][] res = matrixQuick(base, n - 3);
        return (res[0][2] + 2 * res[1][2] + 3 * res[2][2]) % (long) (1E9 + 7);
    }

    public static long[][] matrixQuick(long[][] base, long l)
    {
        long[][] ans = new long[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        while (l != 0)
        {
            if ((l & 1) == 1)
                ans = matrixMul(ans, base);
            base = matrixMul(base, base);
            l >>= 1;
        }
        return ans;
    }

    public static long[][] matrixMul(long[][] ans, long[][] base)
    {
        long MOD = (long) (1E9 + 7);
        long[][] res = new long[ans.length][base[0].length];
        for (int i = 0; i < ans.length; i++)
            for (int j = 0; j < base[0].length; j++)
                for (int k = 0; k < ans[0].length; k++)
                    res[i][j] = (res[i][j] + ((ans[i][k] % MOD) * (base[k][j] % MOD)) % MOD) % MOD;
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long N;
        N = in.nextLong();
        System.out.println(solution(N));
    }
}

CD186 矩阵的最小路径和

/*
 * DP
 * 令dp[i][j]表示为: 从[0,0]到[i,j]最小的路径累加和
 * 则dp[i][j] = dp[i][j] + min(dp[i-1][j], dp[i][j-1])
 */
public class CD186_1
{
    public static int solution(int[][] arr)
    {
        int[][] dp = new int[arr.length][arr[0].length];
        dp[0][0] = arr[0][0];
        for (int i = 1; i < arr.length; i++)
            dp[i][0] = dp[i - 1][0] + arr[i][0];
        for (int i = 1; i < arr[0].length; i++)
            dp[0][i] = dp[0][i - 1] + arr[0][i];
        for (int i = 1; i < arr.length; i++)
            for (int j = 1; j < arr[0].length; j++)
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
        return dp[arr.length - 1][arr[0].length - 1];
    }

    // 状态压缩
    public static int solutionCompress(int[][] arr)
    {
        int[] dp = new int[arr[0].length];
        dp[0] = arr[0][0];
        for (int i = 1; i < arr[0].length; i++)
            dp[i] = dp[i - 1] + arr[0][i];
        for (int i = 1; i < arr.length; i++)
            for (int j = 0; j < arr[0].length; j++)
                if (j == 0)
                    dp[j] = dp[j] + arr[i][j];
                else
                    dp[j] = Math.min(dp[j], dp[j - 1]) + arr[i][j];
        return dp[arr[0].length - 1];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int m, n;
        m = in.nextInt();
        n = in.nextInt();
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                arr[i][j] = in.nextInt();
        System.out.println(solutionCompress(arr));
    }
}

CD12 换钱的最少货币数

/*
* DP
* 令dp[i]表示为凑够i的最少硬币个数
* 则dp[i] = min(dp[i], dp[i - coin] + 1)
*/
public class CD12_1
{
    public static int solution(int[] coins, int aim)
    {
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= aim; i++)
            for (int coin : coins)
                if (i >= coin)
                    dp[i] = (int) Math.min((long) dp[i], dp[i - coin] + 1L);
        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, aim;
        n = in.nextInt();
        aim = in.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++)
            coins[i] = in.nextInt();
        System.out.println(solution(coins, aim));
    }
}

/*
 * 左神版本
 * 通过 minCoins1() -> minCoins2() 的迭代
 * 说明动态规划，即对暴力搜索的优化
 */
public class CD12_2
{
    // 递归解法(自上到下)
    public static int minCoins1(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return -1;
        return process(arr, 0, aim);
    }

    public static int process(int[] arr, int i, int rest)
    {
        if (i == arr.length) return rest == 0 ? 0 : -1;
        int res = -1;
        for (int k = 0; k * arr[i] <= rest; k++)
        {
            int next = process(arr, i + 1, rest - k * arr[i]);
            if (next != -1)
                res = res == -1 ? next + k : Math.min(res, next + k);
        }
        return res;
    }

    // 因为无后效性, 自上到下的解法中存在大量重复计算, 所以改为自下到上
    public static int minCoins2(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return -1;
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        for (int col = 1; col <= aim; col++) dp[N][col] = -1;
        for (int i = N - 1; i >= 0; i--)
        {
            for (int rest = 0; rest <= aim; rest++)
            {
                dp[i][rest] = -1;
                if (dp[i + 1][rest] != -1)
                    dp[i][rest] = dp[i + 1][rest];
                if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1)
                {
                    if (dp[i][rest] == -1)
                        dp[i][rest] = dp[i][rest - arr[i]] + 1;
                    else
                        dp[i][rest] = Math.min(dp[i][rest], dp[i][rest - arr[i]] + 1);
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, aim;
        n = in.nextInt();
        aim = in.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++)
            coins[i] = in.nextInt();
        System.out.println(minCoins2(coins, aim));
    }
}

CD17 机器人达到指定位置方法数❗

/*
 * ❗DP本质❗
 * 暴力递归解决的方法优化成动态规划
 */
public class CD17_1
{
    // 原始方法：通过递归进行暴力穷举
    public static int ways1(int N, int M, int K, int P)
    {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) return 0;
        return walk(N, M, K, P);
    }

    public static int walk(int N, int cur, int rest, int P)
    {
        if (rest == 0) return cur == P ? 1 : 0;
        if (cur == 1) return walk(N, 2, rest - 1, P);
        if (cur == N) return walk(N, N - 1, rest - 1, P);
        return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
    }

    /*  暴力递归解决的方法如何优化成动态规划?
        1）找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了。
        2）把可变参数的所有组合映射成一张表，有 1 个可变参数就是一维表，2 个可变参数就是二维表……
        3）最终答案要的是表中的哪个位置，在表中标出。
        4）根据递归过程的 base case，把这张表最简单、不需要依赖其他位置的那些位置填好值。
        5）根据递归过程非 base case 的部分，也就是分析表中的普遍位置需要怎么计算得到，那么这张表的填写顺序也就确定了。
        6）填好表，返回最终答案在表中位置的值。
     */
    public static int ways2(int N, int M, int K, int P)
    {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) return 0;
        int[][] dp = new int[K + 1][N + 1];
        dp[0][P] = 1;
        for (int i = 1; i <= K; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (j == 1)
                    dp[i][j] = dp[i - 1][2];
                else if (j == N)
                    dp[i][j] = dp[i - 1][N - 1];
                else
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }
        return dp[K][M];
    }

    // 加上取模
    public static long solution(int N, int M, int K, int P)
    {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) return 0;
        int MOD = (int) (1E9 + 7);
        long[][] dp = new long[K + 1][N + 1];
        dp[0][P] = 1;
        for (int i = 1; i <= K; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (j == 1)
                    dp[i][j] = dp[i - 1][2];
                else if (j == N)
                    dp[i][j] = dp[i - 1][N - 1];
                else
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
            }
        }
        return dp[K][M];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, m, k, p;
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        p = in.nextInt();
        System.out.println(solution(n, m, k, p));
    }
}

CD19 换钱的方法数❗

/*
* ❗
* 暴力递归 => 记忆化搜索
* 暴力递归 => DP => 空间压缩
* 因为记忆化搜索方法在本质上等价于动态规划方法。
* 记忆化搜索的方法只是单纯地对计算过的递归过程进行记录，避免重复的递归过程，
* 而动态规划的方法则是规定好每一个递归过程的计算顺序，依次进行计算，后计算的过程严格依赖前面计算过的过程。
* 两者都是空间换时间的方法，也都有枚举的过程，区别就在于动态规划规定计算顺序，而记忆搜索不用规定。
*/
public class CD19_1
{
    // 暴力递归
    public static int coins1(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return 0;
        return process1(arr, 0, aim);
    }

    public static int process1(int[] arr, int index, int aim)
    {
        int res = 0;
        if (index == arr.length) res = aim == 0 ? 1 : 0;
        else
            for (int i = 0; arr[index] * i <= aim; i++)
                res += process1(arr, index + 1, aim - arr[index] * i);
        return res;
    }

    // 备忘录
    public static int coins2(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return 0;
        int[][] map = new int[arr.length + 1][aim + 1];
        return process2(arr, 0, aim, map);
    }

    public static int process2(int[] arr, int index, int aim, int[][] map)
    {
        int res = 0;
        if (index == arr.length) res = aim == 0 ? 1 : 0;
        else
        {
            for (int i = 0; arr[index] * i <= aim; i++)
            {
                int mapValue = map[index + 1][aim - arr[index] * i];
                if (mapValue != 0)
                    res += mapValue == -1 ? 0 : mapValue;
                else
                    res += process2(arr, index + 1, aim - arr[index] * i, map);
            }
        }
        map[index][aim] = res == 0 ? -1 : res;
        return res;
    }

    // DP
    public static int coins3(int[] arr, int aim)
    {
        if (arr == null || arr.length == 0 || aim < 0) return 0;
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) dp[i][0] = 1;
        for (int j = 1; arr[0] * j <= aim; j++) dp[0][arr[0] * j] = 1;
        for (int i = 1; i < arr.length; i++)
        {
            for (int j = 1; j <= aim; j++)
            {
                int num = 0;
                for (int k = 0; j - arr[i] * k >= 0; k++)
                    num += dp[i - 1][j - arr[i] * k];
                dp[i][j] = num;
            }
        }
        return dp[arr.length - 1][aim];
    }

    /*
     * 最终最优化为背包计数
     * 令dp[i]表示为: 有多少种选择方式使得价值正好为 i
     * 则dp[i] += dp[i - coin]
     */
    public static long coins4(int[] arr, int aim)
    {
        long[] dp = new long[aim + 1];
        int MOD = (int) (1E9 + 7);
        dp[0] = 1;
        for (int i = 0; i < arr.length; i++)
        {
            for (int j = aim; j >= 1; j--)
            {
                long num = 0;
                for (int k = 0; j - arr[i] * k >= 0; k++)
                    num = (num + dp[j - arr[i] * k]) % MOD;
                dp[j] = num;
            }
        }
        return dp[aim];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, aim;
        n = in.nextInt();
        aim = in.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++)
            coins[i] = in.nextInt();
        System.out.println(coins4(coins, aim));
    }
}

CD20 打气球的最大分数❗

/*❗❗*/
public class CD20_1
{
    public static int solution1(int[] arr)
    {
        if (arr.length == 1) return arr[0];
        int N = arr.length;
        int[] help = new int[N + 2];
        help[0] = 1;
        help[N + 1] = 1;
        System.arraycopy(arr, 0, help, 1, N);
        return process(help, 1, N);
    }

    public static int process(int[] arr, int L, int R)
    {
        if (L == R) return arr[L - 1] * arr[L] * arr[R + 1];
        int max = Math.max(
                arr[L - 1] * arr[L] * arr[R + 1] + process(arr, L + 1, R),
                arr[L - 1] * arr[R] * arr[R + 1] + process(arr, L, R - 1));

        for (int i = L + 1; i < R; i++)
            max = Math.max(max,
                    arr[L - 1] * arr[i] * arr[R + 1] + process(arr, L, i - 1) + process(arr, i + 1, R));
        return max;
    }

    public static int solution2(int[] arr)
    {
        if (arr.length == 1) return arr[0];
        int N = arr.length;
        int[] help = new int[N + 2];
        help[0] = 1;
        help[N + 1] = 1;
        System.arraycopy(arr, 0, help, 1, N);

        int[][] dp = new int[N + 2][N + 2];
        for (int i = 1; i <= N; i++)
            dp[i][i] = help[i - 1] * help[i] * help[i + 1];
        for (int L = N; L >= 1; L--)
        {
            for (int R = L + 1; R <= N; R++)
            {
                // 最后打爆 help[L]的方案
                int finalL = help[L - 1] * help[L] * help[R + 1] + dp[L + 1][R];
                // 最后打爆 help[R]的方案
                int finalR = help[L - 1] * help[R] * help[R + 1] + dp[L][R - 1];
                dp[L][R] = Math.max(finalL, finalR);
                // 尝试中间位置的气球最后被打爆的每一种方案
                for (int i = L + 1; i < R; i++)
                {
                    dp[L][R] = Math.max(dp[L][R],
                            help[L - 1] * help[i] * help[R + 1] + dp[L][i - 1] + dp[i + 1][R]);
                }
            }
        }
        return dp[1][N];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution2(arr));
    }
}

CD25 最长递增子序列⭐

public class CD25_1
{
    public static int[] solution(int[] arr)
    {
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++)
        {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
                if (arr[i] > arr[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        int len = Integer.MIN_VALUE, index = -1;
        for (int i = arr.length - 1; i >= 0; i--)
        {
            if (len < dp[i])
            {
                len = dp[i];
                index = i;
            }
        }
        int[] ans = new int[len];
        ans[--len] = arr[index];
        for (int i = index - 1; i >= 0; i--)
        {
            if (arr[i] < arr[index] && dp[i] + 1 == dp[index])
            {
                ans[--len] = arr[i];
                index = i;
            }
        }
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        out.println(Arrays.stream(solution(arr)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        out.flush();
    }
}

/* ⭐二分优化⭐ */
public class CD25_2
{
    public static int[] solution(int[] arr)
    {
        int[] dp = new int[arr.length], ends = new int[arr.length];
        ends[0] = arr[0];
        dp[0] = 1;
        int right = 0, l, r, m;
        for (int i = 1; i < arr.length; i++)
        {
            l = 0;
            r = right;
            while (l <= r)
            {
                m = (l + r) / 2;
                if (arr[i] > ends[m])
                    l = m + 1;
                else
                    r = m - 1;
            }
            right = Math.max(right, l);
            ends[l] = arr[i];
            dp[i] = l + 1;
        }
        int len = Integer.MIN_VALUE, index = -1;
        for (int i = arr.length - 1; i >= 0; i--)
        {
            if (len < dp[i])
            {
                len = dp[i];
                index = i;
            }
        }
        int[] ans = new int[len];
        ans[--len] = arr[index];
        for (int i = index - 1; i >= 0; i--)
        {
            if (arr[i] < arr[index] && dp[i] + 1 == dp[index])
            {
                ans[--len] = arr[i];
                index = i;
            }
        }
        return ans;
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        out.println(Arrays.stream(solution(arr)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
        out.flush();
    }
}

CD29 信封嵌套问题

/* 最长上升子序列 */
public class CD29_1
{
    public static class Envelope implements Comparable<Envelope>
    {
        int h;
        int w;

        public Envelope(int h, int w)
        {
            this.h = h;
            this.w = w;
        }

        @Override
        public int compareTo(Envelope o)
        {
            if (this.w != o.w) return this.w - o.w;
            else return o.h - this.h;
        }
    }

    public static int solution(Envelope[] envs)
    {
        Arrays.sort(envs);
        int[] ends = new int[envs.length];
        int right = 0, l, r, m;
        ends[0] = envs[0].h;
        for (int i = 1; i < envs.length; i++)
        {
            l = 0;
            r = right;
            while (l <= r)
            {
                m = (l + r) / 2;
                if (envs[i].h < ends[m])
                    r = m - 1;
                else
                    l = m + 1;
            }
            ends[l] = envs[i].h;
            right = Math.max(l, right);
        }
        return right + 1;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), a, b;
        Envelope[] env = new Envelope[n];
        for (int i = 0; i < n; i++)
        {
            a = in.nextInt();
            b = in.nextInt();
            env[i] = new Envelope(a, b);
        }
        System.out.println(solution(env));
    }
}

CD30 汉诺塔问题⭐

/*⭐*/
public class CD30_1
{
    public static long solution(int arr[])
    {
        return judge(arr, arr.length - 1, 1, 2, 3);
    }

    public static long judge(int[] arr, int idx, int left, int mid, int right)
    {
        if (idx == -1) return 0;
        if (arr[idx] == mid) return -1;
        else if (arr[idx] == left)
            return judge(arr, idx - 1, left, right, mid);
        else
        {
            long res = judge(arr, idx - 1, mid, left, right);
            if (res == -1)
                return -1;
            return (quick(idx) + res) % 1000000007;
        }
    }

    public static long quick(int l)
    {
        long base = 2, ans = 1;
        while (l != 0)
        {
            if ((l & 1) == 1)
                ans = (ans * base) % 1000000007;
            base = (base * base) % 1000000007;
            l >>= 1;
        }
        return ans % 1000000007;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD31 最长公共子序列问题

/*
 * DP
 * 令dp[i][j]表示为: 字符串s1[0...i]与字符串s2[0...j]的最长公共子序列
 */
public class CD31_1
{
    public static String solution(String s1, String s2)
    {
        int[][] dp = new int[s1.length()][s2.length()];
        dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
        for (int i = 1; i < s2.length(); i++)
            dp[0][i] = Math.max(dp[0][i - 1], s1.charAt(0) == s2.charAt(i) ? 1 : 0);
        for (int i = 1; i < s1.length(); i++)
            dp[i][0] = Math.max(dp[i - 1][0], s1.charAt(i) == s2.charAt(0) ? 1 : 0);
        for (int i = 1; i < s1.length(); i++)
        {
            for (int j = 1; j < s2.length(); j++)
            {
                if (s1.charAt(i) == s2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        if (dp[s1.length() - 1][s2.length() - 1] == 0) return "-1";
        int m = s1.length() - 1, n = s2.length() - 1, idx = dp[m][n] - 1;
        char[] ans = new char[dp[m][n]];
        while (idx >= 0)
        {
            if (n > 0 && dp[m][n] == dp[m][n - 1])
                n--;
            else if (m > 0 && dp[m][n] == dp[m - 1][n])
                m--;
            else
            {
                ans[idx--] = s2.charAt(n);
                m--;
                n--;
            }
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s1, s2;
        s1 = in.nextLine();
        s2 = in.nextLine();
        System.out.println(solution(s1, s2));
    }
}

CD33 最长公共子串问题

/*
 * DP
 * 令dp[i][j]表示为: 以字符s1[i]结尾与字符s2[j]结尾的最长公共子串
 */
public class CD33_1
{
    public static String solution(String s1, String s2)
    {
        int[][] dp = new int[s1.length()][s2.length()];
        int maxLen = Integer.MIN_VALUE, idx = -1;
        dp[0][0] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
        for (int i = 1; i < s2.length(); i++)
            dp[0][i] = s1.charAt(0) == s2.charAt(i) ? 1 : 0;
        for (int i = 1; i < s1.length(); i++)
            dp[i][0] = s1.charAt(i) == s2.charAt(0) ? 1 : 0;
        for (int i = 1; i < s1.length(); i++)
        {
            for (int j = 1; j < s2.length(); j++)
            {
                if (s1.charAt(i) == s2.charAt(j))
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (maxLen < dp[i][j])
                    {
                        maxLen = dp[i][j];
                        idx = i;
                    }
                }
            }
        }
        if (idx == -1) return "-1";
        return s1.substring(idx - maxLen + 1, idx + 1);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s1, s2;
        s1 = in.nextLine();
        s2 = in.nextLine();
        System.out.println(solution(s1, s2));
    }
}