【算法题解】 Day25 动态规划

简介: 今天的算法是 「动态规划」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”

剑指 Offer 46. 把数字翻译成字符串

题目

剑指 Offer 46. 把数字翻译成字符串 难度:medium

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 122585种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi""mzi"
AI 代码解读

提示:

  • 0 <= num < 2^31

 

方法一:动态规划

思路

首先我们来通过一个例子理解一下这里「翻译」的过程:我们来尝试翻译「1402」。

分成两种情况:

  • 首先我们可以把每一位单独翻译,即 [1, 4, 0, 2],翻译的结果是 beac
  • 然后我们考虑组合某些连续的两位:

    • [14, 0, 2],翻译的结果是 oac
    • [1, 40, 2],这种情况是不合法的,因为 40 不能翻译成任何字母。
    • [1, 4, 02],这种情况也是不合法的,含有前导零的两位数不在题目规定的翻译规则中,那么 [14, 02] 显然也是不合法的。

那么我们可以归纳出翻译的规则,字符串的第 i 位置:

  • 可以单独作为一位来翻译;
  • 如果第 i1 位和第 i 位组成的数字在 10 到 25 之间,可以把这两位连起来翻译;

我们可以用 f(i) 表示以第 i 位结尾的前缀串翻译的方案数,考虑第 i 位单独翻译和与前一位连接起来再翻译对 f(i) 的贡献。单独翻译对 f(i) 的贡献为 f(i1);如果第 i1 位存在,并且第 i1 位和第 i 位形成的数字 x 满足 10x25,那么就可以把第 i1 位和第 i 位连起来一起翻译,对 f(i) 的贡献为 f(i2),否则为 0。我们可以列出这样的动态规划转移方程:

f(i)=f(i1)+f(i2)[i10,10x25]

边界条件是 f(1)=0f(0)=1。方程中 [c] 的意思是 c 为真的时候 [c] = 1,否则 [c] = 0。

有了这个方程我们不难给出一个时间复杂度为 O(n),空间复杂度为 O(n) 的实现。考虑优化空间复杂度:这里的 f(i) 只和它的前两项 f(i1)f(i2) 相关,我们可以运用「滚动数组」思想把 f 数组压缩成三个变量,这样空间复杂度就变成了 O(1)
 

解题

Python:

class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(len(s) - 2, -1, -1):
            a, b = (a + b if "10" <= s[i:i + 2] <= "25" else a), a
        return a
AI 代码解读

Java:

class Solution {
    public int translateNum(int num) {
        String src = String.valueOf(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.length(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            String pre = src.substring(i - 1, i + 1);
            if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                r += p;
            }
        }
        return r;
    }
}
AI 代码解读

 

后记

📝 上篇精讲: 【算法题解】 Day24 动态规划
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽,期待你的关注;
👍 创作不易,请多多支持;
🔥 系列专栏: 算法题解
目录
打赏
0
0
0
0
0
分享
相关文章
|
15天前
|
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
27 4
算法系列之动态规划
|
5月前
|
深入了解动态规划算法
深入了解动态规划算法
119 1
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
62 5
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
92 8
|
5月前
|
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
193 2
动态规划算法学习三:0-1背包问题
|
4月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
94 2
|
5月前
|
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
115 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等