[leetcode] 134 Gas Station(经典dp

（一）最容易想到的是O（n2）的解法

预处理出gas[i] – cost[i] 的数组，从每个非负的位置开始尝试，只要能够完成一个循环，就可以输出结果；

对于返回-1的情况，我们经过思考和推论可以得出：对于一个循环数组，如果这个数组整体和 SUM >= 0，那么必然可以在数组中找到这么一个元素：从这个数组元素出发，绕数组一圈，能保证累加和一直是出于非负状态。

所以只需要比较sum和0的大小就可以判断是否有解。

（二）继续对问题进行抽象，我们肯定希望一开始的路程都是加油>消耗的，这样就可以累积油量应付后面的消耗量大的，根据这个思路，就转变成求数组的最大连续子序列的和（并且记录起始下标），这是我们前面接触过的题目，例如hdu 1003；

但是因为是循环数组，我们还得考虑一种情况：就是首尾都是正数，怎么办呢？我们只需要再记录并求得 最小连续子序列的和就可以了，最后取Maxsum和sum-Minsum的最大值。另外Minsum的小标要加一取余返回。

class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int sum=0;for(int i=0;i<gas.size();i++){gas[i]=gas[i]-cost[i];sum+=gas[i];}if(sum<0)return -1;int tot1=0,tot2=0;int Maxsum=gas[0],Minsum=gas[0];int Maxpos=0,CurMaxp=0,Minpos=0;for(int i=0;i<gas.size();i++){if(tot1+gas[i]<gas[i]) //最大连续子序列和{tot1=gas[i];CurMaxp=i;}elsetot1+=gas[i];if(tot1>Maxsum){Maxsum=tot1;Maxpos=CurMaxp;}if(tot2+gas[i]>gas[i])//最小连续子序列和tot2=gas[i];elsetot2+=gas[i];if(tot2<Minsum){Minsum=tot2;Minpos=i;}}if(Maxsum>=(sum-Minsum))return Maxpos;elsereturn (Minpos+1)%gas.size();}};（三）还有另外一种简单的思路。我们首先从i站点出发，若走到当前站点cur我们的油量<0，那么只需要从cur+1继续出发试探即可。在此不进行证明，但是我们可以宏观的想一下，前面的任意的前缀站点段的油量和肯定是>0的，那么去掉任意一个前缀，只会使油量变得更少，，所以我们只能尝试从cur+1重新开始。

class Solution {public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int sum=0;for(int i=0;i<gas.size();i++){gas[i]=gas[i]-cost[i];sum+=gas[i];}if(sum<0)return -1;int ans=0,tot=0;for(int i=0;i<gas.size();i++){tot+=gas[i];if(tot<0){ans=i+1;tot=0;}}return ans;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

一个人行走，若是寂寞了，寻一座霓虹灯迷离闪烁，