Recursion -> Memoization -> DP with explanations using Go
Intuition\nDivide the problem into sub problems.\nfor a string s with length n, \n- if s[0]==s[n-1], then f(s) = f(s[1:n-1]) \n- else, f(s) = 1+min(f(s[1:n]), f
# Intuition\nDivide the problem into sub problems.\nfor a string s with length n, \n- if s[0]==s[n-1], then f(s) = f(s[1:n-1]) \n- else, f(s) = 1+min(f(s[1:n]), f(s(:n-1)))\n\nSo we can use recursion to solve this problem\n\n# Approach\nRecursion\n\n# Complexity\n- Time complexity:\nO(2^N) for the worst situation\n\n- Space complexity:\nO(Recursion\'s depth) = O(N)\n\n# Code\n```\nfunc minInsertions(s string) int {\n    n := len(s)\n    if n <= 1 {return 0}\n    if s[0]==s[n-1] {return minInsertions(s[1:n-1])}\n    return 1+min2(minInsertions(s[1:]), minInsertions(s[:n-1]))\n}\nfunc min2(a, b int) int {if a < b {return a} else {return b}}\n```\n\n# Improve with memorization\nAs we can see, recursion\'s time complexity is O(2^N), a lot of same sub problems are repeatedly computed. \ne.g. for the following equation,\n- else, f(s) = 1+min(f(s[1:n]), f(s(:n-1)))\n\nwe can conclude that f(s[1:n-1]) would be computed in both f(s[1:n]) and f(s[:n-1]), so f(s[1:n-1]) is repeatedly computed. And the same situation for every f(s[i:j]) when i>=1 and j<=n-1 and i<j.\n\nWe can use two variables (l, r) to mark one specific sub problem. Imagine function `f` is what we want, `f(0, n-1)` denotes the original problem. In this way, we need compute every sub problem, which is `f(i, j), for every i<j pair`.\n\nMoreover, use some way to store every sub problem\'s result to avoid repeated computing. This is of vital importance to understand further improvements.\n\nSo what we use and how we use it to store every sub problem\'s result?\nThe answer is easy, use the easiest data structure, which is array. Use the\n2D array, dp[i][j] to denote the answer of sub problem `f(i,j)`, which means the answer of f(s[i:j])\n```\nfunc minInsertions(s string) int {\n    n := len(s)\n    dp := make([][]int, n)\n    for i:=0; i<n; i++ {\n        dp[i] = make([]int, n)\n        for j:=0; j<n; j++ {dp[i][j] = -1}\n    }\n\n    var helper func(int, int) int\n    helper = func(l, r int) int {\n        if r-l<=0 {return 0}\n        if dp[l][r] > -1 {return dp[l][r]}\n        if s[l] == s[r] {\n            dp[l+1][r-1] = helper(l+1, r-1)\n            dp[l][r] = dp[l+1][r-1]\n            return dp[l][r]\n        }\n        dp[l][r] = 1 + min2(helper(l+1, r), helper(l, r-1))\n        return dp[l][r]\n    }\n    return helper(0, n-1)\n}\n\nfunc min2(a, b int) int {if a < b {return a} else {return b}}\n```\n\nAt last, we already understand how to use the memoization to solve this\nproblem, we can simplify it one step further.\n\nWe use the bottom-up way, which can help we avoid using recursion.\n\n```\nfunc minInsertions(s string) int {\n    n := len(s)\n    dp := make([][]int, n)\n    for i:=0; i<n; i++ {dp[i] = make([]int, n)}\n\n    for d:=1; d<n; d++ {  // d means distance\n        for i:=0; i+d<n; i++ {\n            if s[i]==s[i+d] {\n                dp[i][i+d] = dp[i+1][i+d-1]\n            } else {\n                dp[i][i+d] = 1 + min2(dp[i][i+d-1], dp[i+1][i+d])\n            }\n        }\n    }\n    return dp[0][n-1]\n}\nfunc min2(a, b int) int {if a < b {return a} else {return b}}\n```\nWe need pay attention to lots of details here. e.g. dp[i][i] is always equal to 0, because dp[i][i] means the ith character of s, and for one character, it is palindrome itself, so dp[i][i] = 0
['Dynamic Programming', 'Recursion', 'Memoization', 'Go']