面试题46. 把数字翻译成字符串

骑猪看日落 2023-02-16 12:14 136阅读 0赞

# 题目： #

[面试题46. 把数字翻译成字符串][46.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

**注意：此题类似于“青蛙跳台阶”一题。**  
![在这里插入图片描述][20200609215740611.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][20200609220031322.png]

# 代码： #

public class 面试题46 { 
    
        public static int translateNum(int num) { 
            String s = String.valueOf(num);
            int dp[] = new int[s.length() + 1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= s.length(); i++)
            { 
                String temp = s.substring(i - 2, i);
                if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
                { 
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                else
                { 
                    dp[i] = dp[i - 1];
                }
            }
            return dp[s.length()];
        }
    
        public static void main(String[] args) { 
            int num = 12258;
            int res = translateNum(num);
            System.out.println(res);
        }
    }

# 参考： #

1.  [面试题46. 把数字翻译成字符串（动态规划，清晰图解）][46. 1]
2.  [把数字翻译成字符串][Link 1]
3.  [【手绘图解】递归>记忆化递归>动态规划>降维][Link 2]

[46.]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609215712893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200609215740611.png]: https://img-blog.csdnimg.cn/20200609215740611.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609215751467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200609215837997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200609215938343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200609215951245.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ==,size_16,color_FFFFFF,t_70
[20200609220031322.png]: https://img-blog.csdnimg.cn/20200609220031322.png
[46. 1]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
[Link 1]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-by-leetcode-sol/
[Link 2]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/shou-hui-tu-jie-dfsdi-gui-ji-yi-hua-di-gui-dong-ta/