O(S*N) Removing 10 factor


#1
class Solution:
    # @param A : integer
    # @param B : integer
    # @return an integer
    def solve(self, n, s):
        dp = [[0 for _ in range(n + 1)] for _ in range(s + 1)]
        for i in range(1, s + 1):
            for j in range(1, n + 1):
                if i == 1:
                    dp[i][j] = 1
                elif j == 1:
                    if 1 <= i <= 9:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = 0
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
                    if i - 10 >= 0:
                        dp[i][j] -= dp[i - 10][j - 1]
        return dp[s][n]%1000000007