本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程解码方法【题目描述】给出一个数字n nn我们按照如下规则把它翻译为字符串0 翻译成 “a” 1 翻译成 “b”…11 翻译成 “l”…25 翻译成 “z”。一个数字可能有多个翻译。请编程计算一个数字有多少种不同的翻译方法。例如102040有4种不同的翻译方法分别是bacaea, “bauea”, “kcaea和kuea”。【输入】一行一个整数n nn【输出】一个整数翻译方法数【输入样例】102040【输出样例】4【核心思想】问题分析给定一个数字字符串s ss每个数字可以单独翻译0→a, 1→b, …, 9→j或者与前一个数字组合成两位数翻译10→k, 11→l, …, 25→z。求不同的翻译方法总数。这是一个线性动态规划问题类似于斐波那契数列的递推关系。算法选择动态规划DPd p [ i ] dp[i]dp[i]表示前i ii个字符的翻译方法数状态转移根据当前字符能否与前一个字符组合决定转移方式关键步骤将输入数字转为字符串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 2i2到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] 1s[i−1]′1′可以组成10 1010-19 1919有效若s [ i − 1 ] ′ 2 ′ s[i-1] 2s[i−1]′2′且s [ i ] ≤ ′ 5 ′ s[i] \leq 5s[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]作为答案时间/空间复杂度时间复杂度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]线性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-一维【代码详解】#includeiostream#includealgorithmusingnamespacestd;string s;// 输入的数字字符串intn,dp[55];// n: 字符串长度dp: 动态规划数组intmain(){cins;// 读入数字字符串ns.size();// 获取字符串长度s s;// 在字符串前加一个空格使下标从1开始dp[0]dp[1]1;// 初始化动态规划数组// dp[0] 1: 空字符串有1种解码方式// dp[1] 1: 第一个字符单独解码有1种方式for(inti2;in;i){// 检查前两个字符是否能组成一个有效的两位数// 条件1: 前一个字符是1则当前字符可以是0-9// 条件2: 前一个字符是2且当前字符小于等于5则组成的数字是20-25if(s[i-1]1||s[i-1]2s[i]5){// 如果前两个字符能组成有效数字则有两种解码方式// 1. 当前字符单独解码dp[i-1]种方式// 2. 前两个字符一起解码dp[i-2]种方式dp[i]dp[i-1]dp[i-2];}else{// 如果前两个字符不能组成有效数字则当前字符必须单独解码dp[i]dp[i-1];}}coutdp[n];// 输出整个字符串的解码方式总数return0;}【运行结果】102040 4
题解：学而思编程 解码方法
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程解码方法【题目描述】给出一个数字n nn我们按照如下规则把它翻译为字符串0 翻译成 “a” 1 翻译成 “b”…11 翻译成 “l”…25 翻译成 “z”。一个数字可能有多个翻译。请编程计算一个数字有多少种不同的翻译方法。例如102040有4种不同的翻译方法分别是bacaea, “bauea”, “kcaea和kuea”。【输入】一行一个整数n nn【输出】一个整数翻译方法数【输入样例】102040【输出样例】4【核心思想】问题分析给定一个数字字符串s ss每个数字可以单独翻译0→a, 1→b, …, 9→j或者与前一个数字组合成两位数翻译10→k, 11→l, …, 25→z。求不同的翻译方法总数。这是一个线性动态规划问题类似于斐波那契数列的递推关系。算法选择动态规划DPd p [ i ] dp[i]dp[i]表示前i ii个字符的翻译方法数状态转移根据当前字符能否与前一个字符组合决定转移方式关键步骤将输入数字转为字符串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 2i2到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] 1s[i−1]′1′可以组成10 1010-19 1919有效若s [ i − 1 ] ′ 2 ′ s[i-1] 2s[i−1]′2′且s [ i ] ≤ ′ 5 ′ s[i] \leq 5s[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]作为答案时间/空间复杂度时间复杂度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]线性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-一维【代码详解】#includeiostream#includealgorithmusingnamespacestd;string s;// 输入的数字字符串intn,dp[55];// n: 字符串长度dp: 动态规划数组intmain(){cins;// 读入数字字符串ns.size();// 获取字符串长度s s;// 在字符串前加一个空格使下标从1开始dp[0]dp[1]1;// 初始化动态规划数组// dp[0] 1: 空字符串有1种解码方式// dp[1] 1: 第一个字符单独解码有1种方式for(inti2;in;i){// 检查前两个字符是否能组成一个有效的两位数// 条件1: 前一个字符是1则当前字符可以是0-9// 条件2: 前一个字符是2且当前字符小于等于5则组成的数字是20-25if(s[i-1]1||s[i-1]2s[i]5){// 如果前两个字符能组成有效数字则有两种解码方式// 1. 当前字符单独解码dp[i-1]种方式// 2. 前两个字符一起解码dp[i-2]种方式dp[i]dp[i-1]dp[i-2];}else{// 如果前两个字符不能组成有效数字则当前字符必须单独解码dp[i]dp[i-1];}}coutdp[n];// 输出整个字符串的解码方式总数return0;}【运行结果】102040 4
