[Golang] O(n) with explanation
Since 1 <= every number <= limit, there are some nature boundaries:\n- For pair sum there\'s a boundary: 2 ~ 2limit.\n- For every valid sum, at most 2 moves.\n\
Since `1 <= every number <= limit`, there are some nature boundaries:\n- For pair sum there\'s a boundary: 2 ~ 2*limit.\n- For every valid sum, at most 2 moves.\n\nIf limit = 5, pair numbers are [3, 4], because every number >= 1, pair sum can only\n greater than itself.\n \nFor number 3, possible sums are:\n 0 1 2 3 4 5 6 7 8\n         <------->\n         \nBecause `1 <= every number <= limit`, so sum can range from 3+1 ~ 3+5\n         \nFor number 4, possible sums are:\n 0 1 2 3 4 5 6 7 8 9\n         <--------->\n         \nCombine above observations, moves can be found as follows:\n - no change: sum = 3+4 = 7\n - 1 change: sum ranges 3+1 ~ 6, 8 ~ 4+5 = 4~6, 8~9\n - 2 moves: 2, 10\n \nFor general case, every pair sum [m, n] has following conditions:\n- no change: m+n\n- 1 change: min(m, n)+1 ~ m+n-1, m+n+1 ~ max(m, n)+limit\n- 2 moves: 2 ~ min(m, n), max(m, n)+limit+2 ~ 2*limit\n\nThe algorithm is straight forward, create a dp array from 0 ~ 2*limit+1, dp[i] means\n moves to make pair of sum equal to i\n\nAs above observations, time complexity of this algorithm is O(n * limit), n is size of\n array\n \n ```golang\nfunc minMoves(nums []int, limit int) int {\n    size := len(nums)\n    \n    // dp[i]: needed moves for pair of sum to i\n    dp := make([]int, limit*2+1)\n    \n    var j, m, n int\n    for i := 0; i < size>>1; i++ {\n        if nums[i] >= nums[size-1-i] {\n            m, n = nums[i], nums[size-1-i]\n        } else {\n            m, n = nums[size-1-i], nums[i]\n        }\n        \n        sum := m+n\n        \n        // [2, 2], 2: 2, 3: 1, 4: 0\n        // need to start from sum, because don\'t know n+1 is 1 or 2 moves\n        for j = sum-1; j >= n+1; j-- {\n            dp[j] += 1\n        }\n        \n        for ; j >= 2; j-- {\n            dp[j] += 2\n        }\n        \n        for j = sum+1; j <= m+limit; j++ {\n            dp[j] += 1\n        }\n        \n        for ; j < len(dp); j++ {\n            dp[j] += 2\n        }\n    }\n    \n    minChange := math.MaxInt32\n    \n    for i := 2; i < len(dp); i++ {\n        if dp[i] < minChange {\n            minChange = dp[i]\n        }\n    }\n    \n    return minChange\n}\n```\n\nThis algorithm gets TLE, next step is to optimize it.\n\nMain loop tries to calculate moves for the specific pair of sum, so it gets a lot of\n addition.\n \n- iteration 1\n    dp = [0, 0, 2, 1, 0, 1, 2, 2]\n    \n- iteration 2\n    dp = [0, 0, 4, 2, 1, 3, 4, 4]\n    \nFor every iteration, dp[i] could only be same as before or larger. Instead of counting\n precisely needed moves for the specific sum, it could also be done by storing\n  increment value.\n  \nTake pair of numbers [3, 4] as an example:\noriginal dp = [0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 2] meaning\n\nsum = 4, moves = 1\nsum = 5, moves = 1\nsum = 6, moves = 1\nsum = 7, moves = 0\nsum = 8, moves = 1\nsum = 9, moves = 1\nsum = 10, moves = 2\n            \nInstead of storing exactly moves, storing increment value forms new dp as follows:\n[0, 0, 0, 0, 1, 0, 0, -1, 1, 0, 1] meaning\n\nsum = 4, count = 0 + 1 = 1\nsum = 5, count = 1 + 0 = 1\nsum = 6, count = 1 + 0 = 1\nsum = 7, count = 1 - 1 = 0\nsum = 8, count = 0 + 1 = 1\nsum = 9, count = 1 + 0 = 1\nsum = 10, count = 1 + 1 = 2\n\nWith this technique, computation can be further reduced, time complexity is O(n)\n\n```golang\nfunc minMoves(nums []int, limit int) int {\n    size := len(nums)\n    \n    // dp[i]: needed moves for pair of sum to i\n    dp := make([]int, limit*2+2)\n    \n    var m, n int\n    for i := 0; i < size>>1; i++ {\n        if nums[i] >= nums[size-1-i] {\n            m, n = nums[i], nums[size-1-i]\n        } else {\n            m, n = nums[size-1-i], nums[i]\n        }\n        \n        sum := m+n\n        \n        dp[2] += 2\n        dp[n+1]--\n        dp[sum]--\n        dp[sum+1]++    // sum could be 2*limit, dp size should be increased\n        dp[m+limit+1]++\n    }\n    \n    minChange := math.MaxInt32\n    var count int\n    \n    for i := 2; i <= limit*2; i++ {\n        count += dp[i]\n        if count < minChange {\n            minChange = count\n        }\n    }\n    \n    return minChange\n}\n```
['Go']