简单动态规划
分析可得,每一位可以有两种状态,0 或者 1,dp[i][0]=dp[i-1][0]+dp[i-1][1],表示 第i位如果 取0 ,那么他的前一位 可以是任意的
dp[i][1]=dp[i-1][0],表示,第i位如果取1 ,那么他的前一位 必须是 0
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[50][2]; int main(){ int n; int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++){ scanf("%d",&n); dp[1][0]=dp[1][1]=1; for(int i=2;i<=n;i++){ dp[i][1]=dp[i-1][0]; dp[i][0]=dp[i-1][0]+dp[i-1][1]; } printf("Scenario #%d:\n",cas); printf("%d\n\n",dp[n][0]+dp[n][1]); } }
这里还有另一种理解思路。
dp[i]有两种状态可以推过来,如果 第i 位为 0 ,那么只要保证 前 i-1 个中没有 连续的 1 就可以,如果 第i位 为 1,那么i-1位肯定要是 0 ,那么只要保证 前 i-2 个数种没有连续的1就可以了,可得状态转移方程,dp[i]=dp[i-1]+dp[i-2],这就是斐波拉契数列啊,啊啊啊。。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[50]={1,2}; int main(){ for(int i=2;i<=45;i++)dp[i]=dp[i-1]+dp[i-2]; int n; int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++){ scanf("%d",&n); printf("Scenario #%d:\n",cas); printf("%d\n\n",dp[n]); } }