动态规划解决 Decode Ways 问题：从理解到实现-平芜编程栈

题目与直观理解

题目给了一段只包含数字的字符串 s，每个数字序列可以通过下面的映射解码成字母：

“1” -> ‘A’，“2” -> ‘B’，…，“25” -> ‘Y’，“26” -> ‘Z’。

比如 “12” 可以解码为 “AB”（1,2）或 “L”（12），所以答案是 2。

但像 “06” 这种因为有前导 0，不能解码成 ‘F’，此时整串无效，返回 0。

问题：给定 s，返回不同解码方式的总数，如果完全无法解码，则返回 0。

LeetCode原题链接

动态规划建模

这类"前缀 + 计数"的问题，非常适合用一维 DP 来建模。

状态定义：设 dp[i] 表示前 i 个字符（s[0…i-1]）的解码总数。

数组大小：字符串长度为 str_len，则 dp 的下标范围是 0…str_len，一共 str_len + 1 个元素。

基础状态：dp[0] = 1，表示空字符串有 1 种"什么都不选"的解码方式，这是后续转移的起点。

有了定义之后，目标就是返回 dp[str_len]，即整个字符串的解码数。

转移方程设计

每次处理到第 i 个字符（1-based），看两种可能的"最后一段"：一位数或两位数。

一位数结尾

取出当前一位：digit_1 = s[i-1] - ‘0’。

如果 1 <= digit_1 <= 9，说明这一位可以单独映射成一个字母，就可以从 dp[i-1] 转移过来：

dp[i] += dp[i-1]

注意：digit_1 为 0 时无效，不能单独解码，所以这一分支要跳过。

两位数结尾

i 至少要大于 1，才能看两位：i > 1。

取出两位数：digit_2 = (s[i-2]-‘0’) * 10 + (s[i-1]-‘0’)。

如果 10 <= digit_2 <= 26，说明这两位可以一起映射成一个字母，就可以从 dp[i-2] 转移过来：

dp[i] += dp[i-2]

这里自然规避了前导 0：比如 “06” 转出来就是 6，不在 10~26 中，所以两位分支也不会被加上。

这样的转移有两个关键点：

使用"+=“而不是”="，因为可能同时存在"一位结尾"和"两位结尾"两种方案，需要累加。
0 的处理是通过判断区间来隐式完成的：一位需要 1~9，两位需要 10~26。

边界与特例思考

实现前要先想清楚几个典型用例：

s = “12”：

dp[0] = 1。
i=1: digit_1=1 → dp[1]+=dp[0]=1。
i=2: digit_1=2 → dp[2]+=dp[1]=1；digit_2=12 → dp[2]+=dp[0]=1，总共 2。

s = “226”：

答案为 3，分别是 “2 2 6”、“22 6” 和 “2 26”。

s = “06”：

i=1: digit_1=0，不在 1~9，dp[1] 仍为 0。
i=2: digit_1=6 → dp[2]+=dp[1]=0；digit_2=6，不在 10~26，dp[2] 还是 0，最终返回 0。

另外还要考虑：

字符串为空或指针为 NULL 时，直接返回 0，防止非法输入。
动态申请 dp 数组后要记得初始化为 0，并在最后释放内存。

完整 C 代码实现

下面是最终通过所有用例、时间 0ms 的 C 语言实现，时间复杂度 O(n)，空间复杂度 O(n)：

intnumDecodings(char*s){inti,str_len,digit_1,digit_2,result;int*dp;if(s==NULL||strlen(s)==0)return0;str_len=strlen(s);dp=(int*)malloc((str_len+1)*sizeof(int));memset(dp,0,(str_len+1)*sizeof(int));dp[0]=1;for(i=1;i<=str_len;i++){digit_1=s[i-1]-'0';if(digit_1>=1&&digit_1<=9)dp[i]+=dp[i-1];if(i>1){digit_2=(s[i-2]-'0')*10+(s[i-1]-'0');if(digit_2>=10&&digit_2<=26)dp[i]+=dp[i-2];}}result=dp[str_len];free(dp);returnresult;}