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)