Sicily: 101.Alphacode

2019-11-06 09:19:05

字体：大中小

来源：转载

供稿：网友

Sicily: 101.Alphacode

动态规划问题。求一串字母转为数字的字符串有多少种解密方法。与斐波那契数列有点像，但是多了几个条件而已。动态转移方程如下：

动态转移方程

if(( array[ i - 1 ] == '1' && array[ i ] <= '9' ) || ( array[ i - 1 ] == '2' && array[ i ] <= '6' ))//i和i-1组合有意义，分开有意义 dp[i]=dp[i-1]+dp[i-2];else if(array[i] > '6' || array[i-1] == '0')//i和i-1组合无意义，分开有意义 dp[i]=dp[i-1];else if(array[i] == '0')//i和i-1组合有意义，分开无意义 dp[i]=dp[i-2];

其中第三个判断array[i]是否为0是一个要注意的点，因为密码总是正确的，那么0之前只能是‘1’或者是‘2’，无论是哪一种，都只能有一种解密方法，所以dp[i]=dp[i-2]。算是题目比较特殊的地方。

代码

#include <iostream> #include <string> using namespace std; int main() { int i; string s; int dp[ 3 ]; while ( cin >> s && s != "0" ) { dp[ 0 ] = dp[ 1 ] = dp[ 2 ] = 1; for ( i = 1; i < s.size(); i++ ) { dp[ 0 ] = dp[ 1 ]; dp[ 1 ] = dp[ 2 ]; if ( s[ i ] == '0' ) dp[ 2 ] = dp[ 0 ]; else if ( ( s[ i - 1 ] == '1' && s[ i ] <= '9' ) || ( s[ i - 1 ] == '2' && s[ i ] <= '6' ) ) dp[ d ] = dp[ 0 ] + dp[ 1 ]; else num[ 2 ] = num[ 1 ]; } cout << num[ 2 ] << endl; } return 0; }

上一篇：r语言怎么将数据标准化和中心化

下一篇：506. Relative Ranks