Lintcode512 Decode Ways solution
2018-04-14 本文已影响0人
程风破浪会有时
【题目描述】
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
有一个消息包含A-Z通过以下规则编码
'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给你一个加密过后的消息，问有几种解码的方式
【题目链接】
www.lintcode.com/en/problem/decode-ways/
【题目解析】
此题可使用动态规划。
设置动态数组dp[n+1]。dp[i]表示从1~i的decode ways的个数。
当给的code只有一位数时，判断是不是valid（A~Z），是的话就dp[1] = 1 不是的话就是dp[1] = 0
因为像给的例子12可以有两种可能的解析方法，所以计算dp[i]的时候要判断两种可能性，再累加。
【参考答案】
