Vacation

题目连结

解题

使用演算法

LCS(Longest Common Subsequence / 找共同子序列)

LCS演算法

程式码(java)

import java.util.*;public class Vacation {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int c = 1;        while (true) {            String s1 = sc.nextLine();            if (s1.equals("#")) {                break;            }            String s2 = sc.nextLine();                        // dp ==> LCS            int[][] dp = new int[s1.length() + 1][s2.length() + 1];            for (int i = 0; i <= s1.length(); i++) {                Arrays.fill(dp[i], 0);            }            for (int i = 0; i < s1.length(); i++) {                for (int j = 0; j < s2.length(); j++) {                    if (s1.charAt(i) == s2.charAt(j)) {                        dp[i + 1][j + 1] = dp[i][j] + 1;                    } else {                        dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);                    }                }            }            System.out.println("Case #" + c + ": you can visit at most " + dp[s1.length()][s2.length()] + " cities.");            c++;        }        sc.close();    }}