动态规划--牛客网19校招--魔法深渊
題目描述
前幾個月放映的頭號玩家簡直火得不能再火了，作為一個探索終極AI的研究人員，月神自然去看了此神劇。
由于太過興奮，晚上月神做了一個奇怪的夢，月神夢見自己掉入了一個被施放了魔法的深淵，月神想要爬上此深淵。
?
已知深淵有N層臺階構成（1 <= N <= 1000)，并且每次月神僅可往上爬2的整數(shù)次冪個臺階(1、2、4、....)，請你編程告訴月神，月神有多少種方法爬出深淵
輸入描述:
輸入共有M行，(1<=M<=1000)第一行輸入一個數(shù)M表示有多少組測試數(shù)據(jù)，接著有M行，每一行都輸入一個N表示深淵的臺階數(shù)輸出描述:
輸出可能的爬出深淵的方式示例1
輸入
復制
4 1 2 3 4輸出
復制
1 2 3 6備注:
為了防止溢出，可將輸出對10^9 + 3取模如果臺階數(shù)為4，每一步可以爬1，2,4,個臺階，則dp[4]=dp[3]+dp[2]+dp[0]
同理有dp[n]=dp[n-1]+dp[n-2]+dp[n-4]+......
一、遞歸的方法（但是本題遞歸在提交時會超時，因此需采用第二種非遞歸的方法）：
#include<stdio.h>
#include<math.h>
int Mod=1000000003;
int Fun(int n)
{
? ? int i=0,sum=0,t,x;
? ? if(n==1)
? ? {
? ? ? ? return 1;
? ? }
? ? if(n==0)
? ? {
? ? ? ? return 1;
? ? }
? ? if (n ==2)
? ? {
? ? ? ? return 2;
? ? }
? ? while(1)
? ? {
? ? ? ? t=pow(2,i);
?? ??? ?if(n-t<0)
?? ??? ?{
?? ??? ??? ?break;
?? ??? ?}
? ? ? ? sum+=Fun(n-t);
? ? ? ? sum%=1000000003;
? ? ? ? i++;
? ? }
? ? return sum;
}
int main()
{
? ? int n,t,i,N;
? ? scanf("%d",&N);
? ? int a[N];
? ? for(i=0;i<N;i++)
? ? {
? ? ?? ?scanf("%d",&n);
? ? ?? ?a[i]=Fun(n);?? ?
?? ?}
?? ?for(i=0;i<N;i++)
?? ?{
?? ??? ?printf("%d\n",a[i]);
?? ?}
}
二、非遞歸
#include<stdio.h>
#include<math.h>
int Mod=1000000003;
int main()
{
? ? int n,t,i;
? ? int dp[1000],j;
? ? dp[0]=1;
? ? dp[1]=1;
? ? for(i=2;i<=1000;i++)
? ? {
? ? ?? ?dp[i]=0;
? ? ?? ?for(j=1;j<=i;j*=2)
? ? ?? ?{
? ? ?? ??? ?dp[i]+=dp[i-j];
? ? ?? ??? ?dp[i]%=Mod;
?? ??? ?}
?? ?}
?? ?int N;
?? ?scanf("%d",&N);
?? ?int a[N];
? ? for(i=0;i<N;i++)
? ? {
? ? ?? ?scanf("%d",&n);
? ? ?? ?a[i]=dp[n];?? ?
?? ?}
?? ?for(i=0;i<N;i++)
?? ?{
?? ??? ?printf("%d\n",a[i]);
?? ?}
}
總結(jié)
以上是生活随笔為你收集整理的动态规划--牛客网19校招--魔法深渊的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
