PROBLEM LINK:
Author: Rezwanul Islam Maruf
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, Math
PROBLEM:
Each charter has assigned by an integer number. Need to find the number of string with length L which charters are sorted with no duplicates charter and sum of the charters is S.
QUICK EXPLANATION:
L and S is large. But with some observation no duplicates charter, we can say that string length should be less or equal 52 (number of lower case and upper case English letter). And that means no string with S greater then 1378.
So dp array should be dp[52][1378]. And the dp should be like classical 0-1 knapsack algorithm when charters are the items and S is the weight.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.