46-把数字翻译成字符串 #

public class Solution {


    //基本思路： 动态规划 按照字符串，1位时候编码，2位时的编码，位数增加后的编码计算

    // 小青蛙跳楼梯的变种
    // 1位数 一种编法
    // 2位数 两种编法，一种是1位+1位，另外一种是两位一起编，不过要判断，要大于等于10，小于等于25,否则无效
    // 3位数 就是 1位数的编法(加两位:需判断) + 2位数的编法+1位
    // 以此类推
    
    public int TranslateNum(int num) {
        char[] str = num.ToString().ToCharArray();;
        int[] dp = new int[str.Length+1];
        dp[0] = 1; // 只有一位的时候，只能有一种编码方式
        dp[1] = 1;
        int maxCount = 1;
        for(int i=2; i < str.Length+1; i++){
            //当前位直接编码，那么和前一种编码算同一个放置，只有联合前面一位的二位编码，才有可能是新编码
            //且如果两位数 > 25 了，那就不能编码，最大是 25 -> z
            int number = Convert.ToInt32(str[i-2].ToString() + str[i-1].ToString()) ;
            if(number <=  25 && number >= 10){
                dp[i] = dp[i-1]+dp[i-2];
            }
            else{
                dp[i] = dp[i-1];
            }
            if(dp[i] > maxCount){
                maxCount = dp[i];
            }
        }

        return maxCount;
    }    
}

public class Solution {
    public int TranslateNum(int num) {
        //动态规划
        // dp[i] 表示前面i位能够编码的方式数
        string str = num.ToString();
        int n = str.Length;
        int[] dp = new int[n+1];
        dp[0] = 1; //前面0位只有一种方式
        dp[1] = 1; //前面1位也只有一种编码方式
        int max = 1;
        for(int i=2; i<=n; i++){
            int preNum = Convert.ToInt32(str[i-2].ToString() + str[i-1].ToString());
            //根据题意如果大于 25的无法编第二种码, 直接 0几 也不算第二种编码，所以 preNum >=10 && preNum <=20 才有可能第二种编码
            if(preNum >=10 && preNum <=25){
                dp[i] = dp[i-2] + dp[i-1];
            }
            else{
                dp[i] = dp[i-1];
            }
            max = Math.Max(dp[i],max);
        }
        return max;
    }
}

public class Solution{
    private int dfs(int num){
        if(num < 10){
            return 1;
        }
        if(num % 100 <= 25 && num %100 >=10){
            //如果余数在10到25之间，那么说明编码可以分为两部分
            //1. 数字除以100的后前面数字的编法 + 这个10~25的编码
            //2. 数字除以10的编法+最后一位数的编码
            //递归处理剩余的部分
            return dfs(num / 10) + dfs(num / 100);
        }
        else{
            return dfs(num / 10);
        }
    }

    public int TranslateNum(int num){
        if(num == 0){
            return 1;
        }
        return dfs(num);
    }
}

public class Solution {
    private int dfs(int num){
        //从后往前编码
        if(num<10){
            return 1;
        }
        if(num % 100 >= 10 && num %100 <=25){
            return dfs(num / 100) + dfs(num / 10);
        }
        else{
            return dfs(num / 10);
        }
    }

    public int TranslateNum(int num) {
        return dfs(num);
    }
}