這道題的題意大概是這樣的：給出一個(gè)字符串，如果將字母表中的26個(gè)字母依次映射成數(shù)字1-26，這樣便形成一個(gè)密碼，a cipher.學(xué)過密碼學(xué)就知道，這是一個(gè)簡單的替代密碼不過似乎并不是那么好用，雖然加密的確很方便，可是解密就麻煩了，因?yàn)榇嬖诤芏喾N解密的方法，所以本題就是要你求出一串?dāng)?shù)字究竟有多少種解密方法。
個(gè)人心得：這是我寒假做的最后幾道題目的其中一道了，一拿到這道題目我就立刻想到了動(dòng)態(tài)規(guī)劃，呵呵，看來偶對(duì)dp開始有點(diǎn)感覺了；
解本題的關(guān)鍵在于將dp[i]裝換成為dp[i-1]和dp[i-2]的關(guān)系
首先確定dp[1]和dp[2]的值 前者肯定等于1 而后者可能為2也可能為1 這個(gè)應(yīng)該很容易判斷出來
然后在判斷i>=3的情況
如果ch[i]為字符‘0’ 那么dp[i]肯定等于dp[i-2].因?yàn)橐粋€(gè)字符不可能被映射成0，它必須和前一個(gè)字符成為一個(gè)整體
如果不是字符零，那么看看這個(gè)字符與前一個(gè)字符是不是能構(gòu)成一個(gè)小于等于26且大于0的數(shù)字
并且這個(gè)數(shù)字的第一位不是0,那么dp[i]=dp[i-1]+dp[i-2];
如果不是讓面的兩種情況 dp[i]=dp[i-1];
這個(gè)題目其實(shí)很容易想到，不過剛做的時(shí)候沒有設(shè)出temp變量，只是規(guī)定兩個(gè)數(shù)字的范圍
'2'>=ch[i-1]>'0'&&ch[i]<='6'這樣19就被和諧掉了所以一直調(diào)都不對(duì)最后才想到的 O(∩_∩)O~
Source Code
Problem: 2033 User: abilitytao
Memory: 272K Time: 16MS
Language: C++ Result: Accepted
#include<iostream>
using namespace std;
long dp[50001];
char ch[50001];
int work(char a[])
{
int temp;
int len;
len=strlen(a);
int i;
dp[0]=1;
temp=(ch[0]-'0')*10+(ch[1]-'0');
if(temp>0&&temp<=26&&ch[1]!='0')
dp[1]=2;
else
dp[1]=1;
for(i=2;i<len;i++)
{
temp=(ch[i-1]-'0')*10+(ch[i]-'0');
if(ch[i]=='0')
dp[i]=dp[i-2];
else if(temp>0&&temp<=26&&ch[i-1]!='0')
dp[i]=dp[i-1]+dp[i-2];
else
dp[i]=dp[i-1];
}
return dp[len-1];
}
int main ()
{
while(cin>>ch)
{
if(ch[0]=='0')
break;
cout<<work(ch)<<endl;
}
return 0;
}