UVA 10446 solution & C++ code

ALGORITHM:

This is an DP problem.

Rather than calculating the value for a particular n and back u store it and when needed dont recalculte.

#include<stdio.h>

unsigned long long dp[70][70];

int ini()
{

    for (int i=0;i<70;i++)
        for (int j=0;j<70;j++)
            dp[i][j]=-1;

    return 0;
}

unsigned long long trib(int n,int back)
{


    if(n<=1)return 1;

    if (dp[n][back]!=-1)return dp[n][back];

    dp[n][back]=1;

    for (int i=1;i<=back;i++)
    {

        dp[n][back]+=trib(n-i,back);
    }
    return dp[n][back];

}


int main(void)

{
    int n,back,kase=1;;


    while (1)
    {

        scanf("%d%d",&n,&back);

        if (n>60)break;

        ini();

        printf("Case %d: %llu\n", kase++,trib(n,back));
    }
    return 0;

}