I think it technically is, if you keep track of which states you've computed and calculate the prefix sum once you've gotten all of them... but it seems super complicated. Just do bottom up. If you don't usually do bottom up, good; this is a great opportunity to learn, since both top-down and bottom-up are useful to know.

So I think those three steps are pretty good; as for the transition, this is where the "local decisions" come into play. If, at a given state, you can break the problem down into making one of multiple choices (often times it's something as simple as "use this element or don't use this element", like in knapsack), then you look at what states you'll end up with in the case of each one of your choices.

Also, as you get to more difficult DP problems, establishing the state starts becoming much harder. For example, for this problem, once you get the state down, the transition is pretty simple, but the state is pretty hard to come up with. In my mind, this is the toughest part :)

Yup, so there should be 1 way of giving 0 coins to 0 children as you said, and 0 ways of giving $$$i > 0$$$ coins to 0 children. You don't need a separate base case for the case of $$$j = 0$$$, since that state should have a transition from dp[i-1][0] anyway.

No that would not happen.

I have submitted solution with this logic at atcoder, it gave me 8 test cases correct and in rest of them (total 16 test cases) it gave me TLE.

The example you provided is an invalid test case (The answer would be 0).

However with a valid example, $$$sum(a_i) >= k$$$. We can do some simple algebraic maipulations and convince ourselves that multiple subtraction would not happen.

Your code here...
 #include<iostream>
#include<cmath>
#include<unordered_map>
#include<math.h>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#include<iomanip>
#include<string>
#include<map>
#define PI 3.14159265
#define mod 998244353  
#define mod1 1000000007  
using namespace std;

// A Dynamic Programming based solution to compute nCr % p 


// Returns nCr % p 
int nCrModp(long long n, long long r, long long p) 
{ 
	// Optimization for the cases when r is large 
	if (r > n - r) 
		r = n - r; 

	// The array C is going to store last row of 
	// pascal triangle at the end. And last entry 
	// of last row is nCr 
	long long C[r + 1] = {0}; 
	  

	C[0] = 1; // Top row of Pascal Triangle 

	// One by constructs remaining rows of Pascal 
	// Triangle from top to bottom 
	for (int i = 1; i <= n; i++) { 

		// Fill entries of current row using previous 
		// row values 
		for (int j = min((long long)(i), r); j > 0; j--) 

			// nCj = (n-1)Cj + (n-1)C(j-1); 
			C[j] = (C[j] + C[j - 1]) % p; 
	} 
	return C[r]; 
} 


void func(){
    long long n , k ;
    cin >> n >> k ;
    //k is the total chocos and n is total no. of student.
     
    long long ans =  nCrModp((n + k - 1) , k , mod1) , arr[n];
    //cout << ans << " ";
    for(int i = 0 ; i < n ; ++i){
        cin >> arr[i];
    }
    long long sum = 0;
    for(int i = 0 ; i < n; ++i){
       // cout << (n + k - 1 - arr[i]) << " " << k - arr[i] << "\n";
        if(arr[i] == k){
            continue;
        }
        else
         sum += nCrModp((n + k - 2 - arr[i]) , k - 1 - arr[i] , mod1);
    }

   
    cout << (ans - sum) % mod1 << "\n";
}   

int main(){
int t = 1 , cnt = 0 ;
//cin >> t;

while(t--){  
    func();
}
}

ans = (ans - MEM(ind-1, left-a[ind-1]-1) + mod)%mod; can you please explain the significance of this line in your code?