[Python] Binomial Problem, DP Top Down w/ Memoization
Main insight: There are two choices at each index, go with "H" or go with "V". The one to choose can be determined by k. \n\nMath prerequisite: How many bitstri
Main insight: There are two choices at each index, go with "H" or go with "V". The one to choose can be determined by k. \n\nMath prerequisite: How many bitstrings can you make with i 0\'s and j 1\'s? nCr(i+j,j). You have i+j slots and j of them must be 1\'s. Out of all these bitstrings, how many of them start with 0? nCr(i+j-1,j). This is because you set the first bit as 0, and you are left with i+j-1 bits remaining to assign, j of them must be ones. How many of the bitstrings start with 1? nCr(i+j-1,j-1), by the same reasoning, i+j-1 bits left to assign, j-1 of them must be 1. \n\nState representation: (i,j,k) as (number of "V"\'s to assign, number of "H"\'s to assign, index of answer). \n\nSo then the recurrence is: If k <= nCr(i+j-1,j-1), then we know that our answer must start with "H". Then, all that is left to do is the assign the rest of the bits, and we make our recursive call. If k > nCr(i+j-1,j-1), then our answer must start with "V", and we subtract nCr(i+1-1,j-1) from k and make recursive call. We can do this subtraction because we bypass all the strings that start with "H", all of which are lexicographically smaller than the strings that start with "V". \n\nThe base case is k = 1, just assign the lexicographically smallest string, using all "H"\'s first then using all "V"\'s. j*"H"+i*"V".\n\nExample: [2,3] k = 9\n\n\t\t\t\t***** (no letters assigned)\n\t\t\t/\t\t\t\t\\ (Go right, k is now 9-6=3, bypassed all leaves on left)\n\t\tH**** \t\t\t\tV****  (nCr(2+2,2)=6<k, so go right.)\n\t\t\t\t\t\t/\t\t\t\\     \n\t\t\t\t\t\tVH***\t\tVV*** (nCr(3,2)=3>=k, go left.)\n\t\t\t\t\t\t\t\t/\t\t\t\\\n\t\t\t\t\t\t\t\tVHH**\t\tVHV** (nCr(2,1)=2<k, go right. k is 1)\n\t\t\t\t\t\t\t\t\t\t\t\t\\\n\t\t\t\t\t\t\t\t\t\t\t\tVHVV* (k is 1, reached base case)\n\nVHVVV is the answer. \n\nO(MN) O(MN), can improve memory by constant multiplier of we do bottom up DP, instead of memoization. \n\nNote: This week\'s contest last 3 problems all are the same flavor of DP. Know what state you are at, define the recurrence relation by possible moves, then perform the recursion by doing those moves.  \n\n```\nfrom math import comb\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        i,j = destination\n        \n        @lru_cache(None)\n        def helper(i,j,k):\n            if k == 1:\n                return "H"*j+"V"*i\n            else:\n                horizontal = comb(i+j-1,j-1)\n                if k <= horizontal:\n                    return "H" + helper(i,j-1,k)\n                else:\n                    return "V" + helper(i-1,j,k-horizontal)\n        \n        return helper(i,j,k)\n```
['Dynamic Programming', 'Python']