是真的一点都不会


私信TA

用户名:dotcpp0702741

访问量:3173

签 名:

等  级
排  名 3562
经  验 1839
参赛次数 0
文章发表 25
年  龄 0
在职情况 学生
学  校 福建农林大学
专  业 空间信息与数字技术

  自我简介:

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

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()];
   }
}


 

0.0分

1 人评分

  评论区