摩尔斯电码解码

1.最开始用递归做的
答案比解多 不知道有没有大佬知道为什么。
可能是递归过程中 对于同一个可能进行了重复计算？

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String mos = in.nextLine();

        int res = recur(mos);
        System.out.println(res);
    }
    public static int recur(String mos){
        if(mos.equals("0")  || mos.equals("1") ){ return 1;}
        if(mos.equals("10") || mos.equals("11")){ return 2;}
        if(mos.equals("100") || mos.equals("101")){ return 3;}
        if(mos.equals("110") ||  mos.equals("111")) { return 4;}

        return  recur(mos.substring(0,mos.length()-1)) +
                recur(mos.substring(0,mos.length()-2)) +
                recur(mos.substring(0,mos.length()-3)) ;
    }
}

2.
字符串 想截取到第i位 就是 substring(i-1,i) 因为是从0开始计算的
在字符串数组中是左闭右开的
第i位 是 数组中的i-1位

看了别人的思路动态规划

知道 111001 可以分三种 （6位）
11100,1
1110,01
111,001
三种分法
后面的就固定不动 不能够再分割了 例如第二行的末尾的01 就不能再拆分为0,1
这样问题就变成了 6位 能否变成 11100 + 1110 + 111 三种解法的和
首先
dp[i]一定等于dp[i-1] 即必定可以拆分为 前面的字符串+1或者0
判断能否 1110,01 这么拆分 如果可以 dp[i] = dp[i-1] + dp[i-2];
主要看i-1位的数值，如果i-1位的数值位0 那么 就不可拆分成01或者00，因为这个不存在，0,0 0,1在上一步已经包含了
如果i-1位的数值位1 那么 后两位就可以拆分为10,11 这是存在的。

i-2 位同理，0开头就不能拆 1开头就可以拆

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String mos = in.nextLine();

        if(mos.length()<2) {
            System.out.println(mos.length());
            return;
        }

        int [] dp = new int [mos.length()+1];

        dp[0] = 1;
        dp[1] = 1;

        for(int i =2 ;i<= mos.length(); i++){
            dp[i] = dp[i-1];
            if(mos.substring(i-2,i-1).equals("1")){
                dp[i] += dp[i-2];
            }
            if(i>=3 && mos.substring(i-3,i-2).equals("1")){
                dp[i] += dp[i-3];
            }
        }
        System.out.println(dp[mos.length()]);
    }
}