light(1232)coin_change_iterative.cpp

#include<bits/stdc++.h>

using namespace std;

#define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
#define mp make_pair
#define pb push_back
#define pii pair<int , int>
#define M 100000007
#define rep(i , n) for(i = 0 ; i< n ;i++ )
#define repi(i , n ) for(i = 1 ; i<= n ; i++ )
#define mem(x , y ) memset(x , y , sizeof x )
#define mx 101
#define ff first
#define ss second

//int dx[] = { -1 ,+1, 0 , 0 , -1 , -1  , 1 , 1 };
//int dy[] = { 0 , 0, +1, -1  , +1 , -1 , 1 , -1 };

//int dx[] = { 1 , 1, 2 , 2  , -1 , -1 , -2 , -2 }; // knight direction
//int dy[] = { 2 , -2, +1, -1 ,2 , -2 , 1 , -1 };
int arr[101], dp[101][10001 ];

int main()
{
    //freopen("in.txt" ,"r" , stdin );

    int i, j, k, cs= 0, tc ;
    scanf("%d ", &tc) ;

    while(tc-- )
    {
        int n  ;
        scanf("%d%d",&n,&k );

        repi(i, n ) scanf("%d", &arr[i] );

        for(i =0 ; i <= k ; i++ )  dp[0][i] =  0;
        for(i = 0 ; i <= n ; i++ )  dp[i][0] = 1 ;

        for(i = 1 ; i<= n ; i++)
            for(j = 1; j <= k ; j++ )
            {
               if(j >= arr[i]  )
                {
                    dp[i][j] = (dp[i-1][j]%M + dp[i][j -  arr[i] ]% M)%M ;
                }
                else dp[i][j] =  dp[i-1][j]%M ;

            }
        printf("Case %d: %d\n",++cs,dp[n][k ]);
    }
    return 0;
}