How to count number of bracket sequences with n opening brackets and m closing brackets so that the balance never gets negative? I came to this problem thinking about other one(D from previous Open Cup), and I can't solve it in sufficient complexity. Is there a way to do it with n <= 2000, m <= 2000, answering one query in O(1) time or somehow precomputing these values for all i, j <= 2000?
May be Catalan number can be useful for you. You can read it here.
Non-negative partial sum
Thank you)