Complexity of a memoized DP with an extra state dimension

Consider 'longest increasing subsequence allowing up to k deletions': dp(i, d) is the length of the best increasing subsequence considering only the first i elements, having used exactly d of the allowed k deletions so far. The transition for dp(i, d) considers every earlier index j < i as a possible predecessor (an O(i) scan), for each of O(n) values of i and O(k) values of d. Memoized top-down (each (i,d) pair computed once), what is the overall time complexity?

24 of 46 in Data Structures & Algorithms