[Python] 2D DP from top-down to bottom-up
dp[i][j] is the solution with finger 1 at position i and finger 2 at position j, initially both at -1.\n\nWhile fingers at [i,j], the next character position is
`dp[i][j]` is the solution with finger 1 at position `i` and finger 2 at position `j`, initially both at `-1`.\n\nWhile fingers at `[i,j]`, the next character position is `k = max(i,j) + 1`, so the recursive formula is \n```\ndp[i][j] = min(dist(word[i], word[k]) + dp[k][j], dist(word[j], word[k]) + dp[i][k])\n```\n\nbottom-up with memorization\n\n```python\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        n = len(word)\n        memo = {}\n        \n        def dist(a, b):\n            x1, y1 = divmod(ord(a) - ord(\'A\'), 6)\n            x2, y2 = divmod(ord(b) - ord(\'A\'), 6)\n            return abs(x1-x2) + abs(y1-y2)\n        \n        def dp(i, j):\n            if (i,j) in memo:\n                return memo[(i,j)]\n            \n            k = max(i, j) + 1\n            if k == n:\n                return 0\n            \n            c = word[k]\n            a = word[i if i >= 0 else k]\n            b = word[j if j >= 0 else k]\n            \n            k1 = dist(a, c) + dp(k, j)\n            k2 = dist(b, c) + dp(i, k)\n            \n            memo[(i,j)] = min(k1,k2)\n            return memo[(i,j)]\n        \n        return dp(-1,-1)\n```\n\nunrolling to get top-down version\n\n```python\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        \n        def dist(a, b):\n            x1, y1 = divmod(ord(a) - ord(\'A\'), 6)\n            x2, y2 = divmod(ord(b) - ord(\'A\'), 6)\n            return abs(x1-x2) + abs(y1-y2)\n\n        n = len(word)\n        dp = [[0] * (n+1) for _ in range(n+1)]\n        \n        for i in range(n-1,-1,-1):\n            for j in range(n-1,-1,-1):\n                k = max(i, j) + 1\n                ii = k if not i else i\n                jj = k if not j else j\n                a = dist(word[ii-1], word[k-1]) + dp[k][j]\n                b = dist(word[jj-1], word[k-1]) + dp[i][k]\n                dp[i][j] = min(a,b)\n        return dp[0][0]\n```
[]