Leetcode 动态规划 Decode Ways

本文为senlie原创，转载请保留此地址：

 Total Accepted: 8689 Total

Submissions: 55465

A message containing letters from <code>A-Z</code> is

being encoded to numbers using the following mapping:

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message <code>"12"</code>, it could be decoded as <code>"AB"</code> (1

2) or <code>"L"</code> (12).

The number of ways decoding <code>"12"</code> is

2.

题意：将A-B编码为1-26，现在给一串数字，问有多少种解码方式

思路：动态规划

设f[i]表示以第i个字符结尾的数字串的解码方式，则

如果 s[i - 2]是1 或 s[i - 2]是2且s[i - 1]小于6，f[i] = f[i - 1] + f[i - 2] 

否则，f[i] = f[i - 1]

此外，还要再加一些判断

如果s[i - 1]是零，则以s[i - 2]数字结尾的解码方式为零。因为s[i - 2]数字必须和s[i - 1]结合起来

实现的时候只要两个变量保存前两个的值，即f[i - 1]和f[i - 2]

注：动态规划，除了那些最后要从所有的f[i]中选出最大最小值的问题，

都只需要用几个变量保存前几个值即可。这样实现不仅省空间，而且不用担心

下标越界

--》其实即使是要求最值的问题，也可以用一个变量表示当前最值，然后在循环中每次更新

复杂度：时间O(n)， 空间O(1)