Ruby solution with memoization
Intuition\nUse memoization -- there\'s a limited number of possibilities.\n\n# Approach\n1. Create a memo and store n as a class variable.\n2. Create an array o
# Intuition\nUse memoization -- there\'s a limited number of possibilities.\n\n# Approach\n1. Create a memo and store n as a class variable.\n2. Create an array of dirs corresponding the the knight\'s possible moves.\n3. Find the probability with a helper function\n\nHelper function:\n1. Return 0 if it\'s off the board, 1 if it\'s on the board and out of moves, and the memoized value if it exists\n2. Look at the 8 possibile knight moves and find the probability of each, then add those together.\n3. Divide the answer by 8.0 (there are eight knight moves, and 8.0 makes it a float), memoize, and return.\n\n# Complexity\n- Time complexity:\n$$O(n^2 * k)$$\n\n- Space complexity:\n$$O(n^2 * k)$$\n\n# Code\n```\ndef knight_probability(n, k, row, column)\n    @memo = {}\n    @n = n\n    @dirs = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]]\n    prob(row,column,k)\nend\n\ndef prob(i,j,k)\n    return 0 unless (0...@n).cover?(i) && (0...@n).cover?(j)\n    return 1 if k == 0\n    return @memo[[i,j,k]] if @memo[[i,j,k]]\n\n    total = 0\n    @dirs.each { |dir| total += prob(i+dir[0],j+dir[1],k-1) }\n\n    @memo[[i,j,k]] = total / 8.0\nend\n```
['Ruby']