Uva 10446【递推,dp】

UVa 10446

求(n,bcak)递归次数。自己推出来了一个式子:

    Uva 10446【递推,dp】

其实就是这个式子,但是不知道该怎么写,怕递归写法超时。其实直接递推就好,边界条件易得C(0,back)=1、C(1,back)=1。

Reference Code:

 #include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ll;
ll dp[][]={}; int main()
{
int n,back;
for(int i=;i<=;i++)
for (int j=;j<=;j++)
dp[i][j]=;
for(int i=;i<=;i++)
for (int j=;j<=;j++){
ll sum=;
for(int k=;k<=j;k++)
if(i-k<) sum+=;
else sum+=dp[i-k][j];
dp[i][j]=sum+;
}
int cas=;
while(scanf("%d%d",&n,&back)==)
{
if(n>) break;
if(n<) n=;
cout<<"Case "<<cas++<<": "<<dp[n][back]<<endl;
}
return ;
}

Reference Blog:http://knightzone.org/?p=1408

上一篇:java堆栈


下一篇:17-TypeScript代理模式