动态规划-公共子序列java

解题思路:
动态规划问题，首先要解决输入一对字符然后计算出结果，所以我这里用

while（sc.hasnext()）{   //当有输入的时候就不停止

//直接调用计算的方法然后打印

}

这里我们需要注意到题目要求的是求最大字串，所以

dp[][]比较str1和str2的时候是用Math.max( ... )

注意事项:
动态规划非常需要注意的就是dp数组的大小以及递归逻辑

参考代码:

import java.util.Scanner;

public class Main {
   static Scanner sc = new Scanner(System.in);

   public static void main(String[] args) {
       while (sc.hasNext()) {

           //传递两个字符串
           int sum = number(sc.next(), sc.next());
           System.out.println(sum);
       }
   }

   public static int number(String str1, String str2) {
       int[][] dp = new int[str1.length() + 1][str2.length() + 1];
       for (int i = 0; i <= str1.length(); i++) {
           dp[i][0] = 0;
       }
       for (int j = 0; j <= str2.length(); j++) {
           dp[0][j] = 0;
       }

       for (int i = 1; i <= str1.length(); i++) {
           for (int j = 1; j <= str2.length(); j++) {

                //当str1[i]==str2[j]的时候，dp值+1

               //不等的时候 此时的dp值就是str1和str2对比之下记录的上一个dp值谁最大然后赋值给现在的dp[i][j]

               if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
               } else {
                   dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
               }
           }
       }
       return dp[str1.length()][str2.length()];
   }
}