http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1463

code應該很好懂

注意一下條件判斷就好了

#include <stdio.h>  
#include <string.h>  

char s[10001];  
long long dp[10001];  
int l;  
long long dfs(int n)  
{  
 if (dp[n] >= 0) {  
 return dp[n];  
 }  
 if (s[n] == '0') {  
 return dp[n] = 0;  
 }  
 if (n == l - 1) {  
 return dp[n] = 1;  
 }  
 if (n == l - 2) {  
 if (s[n] > '2' || s[n] == '2' && s[n + 1] > '6') {  
 return dp[n] = dfs(n + 1);  
 } else {  
 return dp[n] = dfs(n + 1) + 1;  
 }  
 }  
 if (s[n] > '2' || s[n] == '2' && s[n + 1] > '6') {  
 return dp[n] = dfs(n + 1);  
 }  
 return dp[n] = dfs(n + 1) + dfs(n + 2);  
}  
int main()  
{  
 while (gets(s) != NULL) {  
 if (strcmp(s, "0") == 0) {  
 return 0;  
 }  
 l = strlen(s);  
 memset(dp, -1, sizeof(dp));  
 printf("%lld\n", dfs(0));  
 }  
}