Solving some dynamic programming problem

     Today I am going to explain solution of this problem : http://www.spoj.com/problems/BEHAPPY/
Before going to read this article, I would recommend you to read
1. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

2. http://apps.topcoder.com/forums/?module=Thread&threadID=700080&start=0

3. http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0
4. http://apps.topcoder.com/forums/?module=Thread&threadID=697925&start=0

     Now let us see the problem. It says that no of ways of arraning a_1 + a_2 + ... a_m  = n.
where A[i] <= a_i <= B[i].
Note the ranges : 1<=M<=20, 1<=N<=100, 0<=Ai,Bi,<=100

    If you try to check every possible, then it is going to surely going to time out. Finding time complexity of naive approach is left to reader. For solving this problem, you can use maximal matching. But here I would describe only dp algorithm.

1.    Let dp[i][j] denotes the  no of ways of arranging when you have assigned upto i - 1 places and trying to assign i th place.  
2.    From state dp[I][j] by matching I and j, you can go to state dp[I + 1][j + 1]. By not matching, you can go to dp[I][j + 1]. Coding this is very easy and complexity is O(n*n).