企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：解码方法

【题目描述】

给出一个数字n nn，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，…，11 翻译成 “l”，…，25 翻译成 “z”。一个数字可能有多个翻译。请编程计算一个数字有多少种不同的翻译方法。

例如102040有4种不同的翻译方法：分别是"bacaea", “bauea”, “kcaea"和"kuea”。

【输入】

一行，一个整数n nn

【输出】

一个整数，翻译方法数

【输入样例】

102040

【输出样例】

4

【核心思想】

1. 问题分析：给定一个数字字符串s ss，每个数字可以单独翻译（0→a, 1→b, …, 9→j），或者与前一个数字组合成两位数翻译（10→k, 11→l, …, 25→z）。求不同的翻译方法总数。这是一个线性动态规划问题，类似于斐波那契数列的递推关系。

2. 算法选择：

   • 动态规划（DP）：d p [ i ] dp[i]dp[i]表示前i ii个字符的翻译方法数
   • 状态转移：根据当前字符能否与前一个字符组合，决定转移方式

3. 关键步骤：

   • 将输入数字转为字符串s ss，下标从1 11开始
   • 初始化：d p [ 0 ] = 1 dp[0] = 1dp[0]=1（空字符串有1 11种解码方式），d p [ 1 ] = 1 dp[1] = 1dp[1]=1（第一个字符单独解码）
   • 状态转移（从i = 2 i = 2i=2到n nn）：
     • 检查s [ i − 1 ] s[i-1]s[i−1]和s [ i ] s[i]s[i]能否组成有效两位数（10 1010到25 2525）：
       • 若s [ i − 1 ] = ′ 1 ′ s[i-1] = '1's[i−1]=′1′：可以组成10 1010-19 1919，有效
       • 若s [ i − 1 ] = ′ 2 ′ s[i-1] = '2's[i−1]=′2′且s [ i ] ≤ ′ 5 ′ s[i] \leq '5's[i]≤′5′：可以组成20 2020-25 2525，有效
     • 若能组合：d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2]
       • d p [ i − 1 ] dp[i-1]dp[i−1]：s [ i ] s[i]s[i]单独解码的方法数
       • d p [ i − 2 ] dp[i-2]dp[i−2]：s [ i − 1 ] s[i-1]s[i−1]和s [ i ] s[i]s[i]组合解码的方法数
     • 若不能组合：d p [ i ] = d p [ i − 1 ] dp[i] = dp[i-1]dp[i]=dp[i−1]（只能单独解码）
   • 输出d p [ n ] dp[n]dp[n]作为答案

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，只需遍历字符串一次
   • 空间复杂度：O ( n ) O(n)O(n)，使用d p dpdp数组（可优化至O ( 1 ) O(1)O(1)，只保留d p [ i − 1 ] dp[i-1]dp[i−1]和d p [ i − 2 ] dp[i-2]dp[i−2]）

5. 线性DP与类斐波那契递推的核心思想：

   • 最优子结构：前i ii个字符的解码数只与前i − 1 i-1i−1和i − 2 i-2i−2个字符有关
   • 状态转移分情况：根据当前字符能否与前一个组合，决定是单步走还是双步走
   • 边界条件处理：d p [ 0 ] dp[0]dp[0]和d p [ 1 ] dp[1]dp[1]的初始化是递推的基础
   • 适用于字符串解码、爬楼梯、分割整数等组合计数问题

【算法标签】

#线性DP-一维

【代码详解】

#include<iostream>#include<algorithm>usingnamespacestd;string s;// 输入的数字字符串intn,dp[55];// n: 字符串长度，dp: 动态规划数组intmain(){cin>>s;// 读入数字字符串n=s.size();// 获取字符串长度s=' '+s;// 在字符串前加一个空格，使下标从1开始dp[0]=dp[1]=1;// 初始化动态规划数组// dp[0] = 1: 空字符串有1种解码方式// dp[1] = 1: 第一个字符单独解码有1种方式for(inti=2;i<=n;i++){// 检查前两个字符是否能组成一个有效的两位数// 条件1: 前一个字符是'1'，则当前字符可以是0-9// 条件2: 前一个字符是'2'且当前字符小于等于'5'，则组成的数字是20-25if(s[i-1]=='1'||s[i-1]=='2'&&s[i]<='5'){// 如果前两个字符能组成有效数字，则有两种解码方式：// 1. 当前字符单独解码：dp[i-1]种方式// 2. 前两个字符一起解码：dp[i-2]种方式dp[i]=dp[i-1]+dp[i-2];}else{// 如果前两个字符不能组成有效数字，则当前字符必须单独解码dp[i]=dp[i-1];}}cout<<dp[n];// 输出整个字符串的解码方式总数return0;}

【运行结果】

102040 4