题解 | #把数字翻译成字符串#

动态规划题解

问题定义：dp[i]表示长度为i的字符串有多少种匹配方式

递推公式推理：字符只有两位，所以当前i这个位置的问题是由：1.当前选i为一个字母；2.选i和i-1组合一起作为字母；得出递推公式 dp[i] = dp[i-1] + dp[i-2]

*组合时注意的情况，是从1-26编号，选一个数组为0不能递推，组合数小于10大于26不能递推

import java.util.*;

public class Solution {
    public int solve (String nums) {
       int[] dp = new int[nums.length() + 1];
       int temp;
        
       dp[0] = 1;
       if(nums.charAt(0) - '0' >0)dp[1] = 1;
       else dp[1] = 0;//如果第一个字母为0不算一种情况
       
        for(int i = 2; i < nums.length()+1; i++) {
           temp = nums.charAt(i-1)-'0';
           if(temp > 0)dp[i] += dp[i-1];
           
           temp = nums.charAt(i-1)-'0' + (nums.charAt(i-2)-'0')*10;
           if(temp>=10&&temp<=26)dp[i]+=dp[i-2];
       }
        return dp[nums.length()];
    }
}