题目要求不能用除法，只能老老实实乘。

记 left[i] 为从左乘到 a[i-1]，right[i] 为从右乘到 a[i+1]，则 res[i] = left[i]*right[i] 。

由于 left[i] 和 right[i] 都只依赖前一个状态，因此可以用一个变量来代替数组。

这道题给人一种强烈的DP的感觉。实际上，遍历数组求和也能看做是DP的简化，把这道题当做DP来看也没问题的，只不过太简单了，tag里都没有DP。

class Solution {public:    vector
     
       productExceptSelf(vector
      
       & nums) {        // left[i]*right[i]        int n=nums.size();        vector
       
         left(n,1), right(n,1);        for (int i=1;i
        
         =0;--i)            right[i] = right[i+1]*nums[i+1];        vector
         
           res(n);        for (int i=0;i
         
        
       
      
     

 

class Solution {public:    vector
     
       productExceptSelf(vector
      
       & nums) {        // left[i]*right[i]        int n=nums.size();        int left=1, right=1;        vector
       
         res(n,1);        for (int i=1;i
        
         =0;--i){            right *= nums[i+1];            res[i] *= right;        }        return res;    }};