剑指offer46 把数字翻译成字符串【DP】
题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:
1 | 输入: 12258 |
提示:
0 <= num < 231
解题思路
方法一:动态规划
先将数字转化为字符串进行,进而判断连续的两个字符组成的两位字符串是否在10~25的范围内,分为两种情况进行动态规划。
动态规划的转移方程为:
分为两种情况:
- 第一种:第i位和第i-1位字符组成字符串在 10~25范围内,则
$$
dp[i]=dp[i-1]+dp[i-2]
$$
- 第二种:第i位和第i-1位字符组成字符串不在 10~25范围内,则
$$
dp[i]=dp[i-1]
$$
此题可对数组优化为两个变量进行。
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
资源
剑指offer46 把数字翻译成字符串【DP】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.