Dynamic  programming O(n^2*fuel)  | Easy Explanation | C++
Let\'s create array dp[N][Fuel+1], where N = number of locations\nAt first, we stand at the start and have some fuel, so lets put dp[start][fuel] = 1\nNext, for
Let\'s create array **dp[N][Fuel+1]**, where N = number of locations\nAt first, we stand at the start and have some fuel, so lets put **dp[start][fuel] = 1**\nNext, for every possible quantity of fuel and location, we try to find from where we could come here and increase dp[][] for this fuel and location. At the end we just sum up all possible routes, that end in finish and have any amount of fuel;\n\n```\nconst int MOD = 1e9+7;\nint n = locations.size();\nvector<vector<int>>dp(n, vector<int>(fuel+1, 0);\n\ndp[start][fuel] = 1;\n\nfor(int f=fuel; f>=0; --f)\n\tfor(int i=0;i<n; ++i)\n\t\tfor(int j=0;j<n; ++j)\n\t\t\tif(i!=j){\n\t\t\t\tint need = abs(locations[i]-locations[j]);\n\t\t\t\tif (f+need<=fuel){\n\t\t\t\t\tdp[i][f]=(dp[i][f]+dp[j][f+need])%MOD;\n\t\t\t\t} \n}\n        \nlong long ans = 0;\nfor(int i=0;i<=fuel; ++i)\n\tans=(ans+dp[finish][i])%MOD;\nreturn ans;\n```\n\n\n\nThat\'s all, complexity **O(N^2 * fuel)**, memory **O(n * fuel).**\n\nGood luck!\n\n\n
['Dynamic Programming', 'C']