General solution for k moves using recursion and dp
Intuition\nWe are Supposed to return difference(minimum) between smallest and largest number. It immediately strikes sorting! After sorting we will be able to g
# Intuition\nWe are Supposed to return difference(minimum) between smallest and largest number. It immediately strikes sorting! After sorting we will be able to get minimum and maximum number without traversing. To lower the difference we have to either increase the minimum number or decrease the maximum element. And at a time, we can only do either of them. So by using recursion we are taking cases like if we removed start element, or if we removed end element then returning minimum of them. Pure Recursion will give pretty bad solution with time complexity O(2^n) hence we use dp to optimize it to O(n^2), although we can do this question in O(nlogn), I though this solution is pretty easy to figure out, without playing with indexes. \n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPretty much self explainatory!\nK is the number of moves.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity will be O(n^2*k)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n*k)\n\n# Code\n```\nclass Solution {\npublic:\n   int helper(vector<int>& nums, int moves,int start,int end,vector<vector<int>>& dp){\n        if(moves==0){\n            return nums[end]-nums[start];\n        }\n        if (dp[start][moves]!=-1) {\n                 return dp[start][moves];\n            }\n        int remStart=helper(nums,moves-1,start+1,end,dp);\n        int remEnd=helper(nums,moves-1,start,end-1,dp);\n        return dp[start][moves]=min(remStart,remEnd);\n   }\n    int minDifference(vector<int>& nums) {\n        int n=nums.size();\n        if(n<=4){\n            return 0;\n        }\n        //k is number of moves\n        int k=3;\n        sort(nums.begin(),nums.end());\n         vector<vector<int>> dp(n, vector<int>(k + 1, -1));\n        return helper(nums,3,0,nums.size()-1,dp);\n        \n    \n    }\n\n};\n```
['C++']