DP(记忆化搜索)
第一次在Ural做题，所以选个简单的DP，无奈变量写错WA了两次，终于AC了
题意：输入n和k，表示一个n位的k进制数，这个数字要符合两个条件，没有前导0（否则怎么算是n位数呢？），不能有两个或以上连续的0，问你一共有多少个这样的n位的k进制数
这题，最直观的方法就是dfs，不断枚举，枚举到第n层就功德圆满了，然后再判断这个n位数是否符合我们的要求。但是可想而知是会超时的，那么怎么优化呢？第一，当前位的数字决定了下一位能出现什么数字，如果当前位非0，那么下一位[0,k-1]都可以，如果当前位为0则下一位[1,k-1]，这样就可以在枚举的过程中避免掉两个连续的0的情况
但是这个优化不够，最重要的是避免重复的递归，这个就是记忆化搜索的作用。
dp[i][j]表示当前是第i位，数字j，能有多少种情况
当j=0 ， dp[i][j]=dp[i+1][1]+dp[i+1][2]……dp[i+1][k-1]
当j!=0, dp[i][j]=dp[i+1][0]+dp[i+1][1]+dp[i+1][2]……dp[i+1][k-1]
最后的答案就是 ans=dp[1][1]+dp[1][2]……+dp[1][k-1]
要想写成递推的话也是很容易的，但是觉得记忆化更好
#include <cstdio> #include <cstring> const int N=20; int dp[N][N]; //dp[i][j]表示第i位为j的时候的个数 int n,k; void dfs(int c ,int m ) { if(dp[c][m]!=-1) return ; dp[c][m]=0; for(int i=1; i<k; i++) //这些是必然可以枚举的 { dfs(c+1,i); dp[c][m]+=dp[c+1][i]; } if(m) //当前位不为0，那么下一位可以为0; { dfs(c+1,0); dp[c][m]+=dp[c+1][0]; } return ; } int main() { int ans; while(scanf("%d%d",&n,&k)!=EOF) { memset(dp,-1,sizeof(dp)); for(int i=0; i<=k; i++) dp[n][i]=1; ans=0; for(int i=1; i<k; i++) { dp[1][i]=0; for(int j=0; j<k; j++) { dfs(2,j); dp[1][i]+=dp[2][j]; } ans+=dp[1][i]; } printf("%d\n",ans); } return 0; }
这题的本质其实只是分了0和非0，所以我们可以压缩一下空间，用递推来时间，速度更快点
#include <cstdio> #include <cmath> long long dp[20][2]; int main() { int N,K; while(scanf("%d%d",&N,&K)!=EOF) { dp[1][0]=0; dp[1][1]=K-1; for(int i=2; i<=N; i++) { dp[i][1]+=(K-1)*(dp[i-1][1]+dp[i-1][0]); dp[i][0]=dp[i-1][1]; } printf("%lld\n",dp[N][1]+dp[N][0]); } return 0; }