Docode 问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Docode 问题

Docode 问题# JobHunting - 待字闺中

v*e2015-09-07 07:09

1 楼

Given a mapping between numbers and alphabets . Find the number of ways to
decode a sequence of numbers
eg: a - 21 b - 2 c - 54 d - 5 e -4 f-1
2154
1) ac
2) ade
3) bfc
4) bfde
4 ways to decode
http://stackoverflow.com/questions/15586047/given-an-encoded-me
SF上有人用DP解答，并用如下递推公式：Way[n] = Way[n-1] + Way[n-2] 请问这个公
式是如何得出的。如果在上例中有三位数字对应的字母，是不是可以演变成Way[n] =
Way[n-1] + Way[n-2] + Way[n-3]? 这是为什么呢？

x*g2015-09-07 07:09

2 楼

这个参见 leetcode climbing stairs
那个答案不对啊，如果有一个substr 无法翻译就需要改动了，不过也好改。

【在 v****e 的大作中提到】

: Given a mapping between numbers and alphabets . Find the number of ways to
: decode a sequence of numbers
: eg: a - 21 b - 2 c - 54 d - 5 e -4 f-1
: 2154
: 1) ac
: 2) ade
: 3) bfc
: 4) bfde
: 4 ways to decode
: http://stackoverflow.com/questions/15586047/given-an-encoded-me

v*e2015-09-07 07:09

3 楼

我也觉得有点问题。不过只需要把每一项乘以一个bool值再相加。
bool值代表着是否可以被翻译。

【在 x****g 的大作中提到】

: 这个参见 leetcode climbing stairs
: 那个答案不对啊，如果有一个substr 无法翻译就需要改动了，不过也好改。