Intuition for this problem


#1

This is problem is basically a combination of Longest Increasing Subsequence and Coin Change problem. With a small optimization you can reduce the time complexity from O(nk^2) to O(nk).