[数据结构与算法]leetcode-DP

413. Arithmetic Slices

Link

解法1： 动态规划

感觉dp还是好难想好难想！什么时候用dp呢？就是在当前状态会受上一次影响的情况下。
此题就是，如果上一次为等差数列，而这次又满足条件，就可以一直递归下去
dp[i]表示从num【0】到num【i】有多少以num【i】结尾的等差子数列
这个以num【i】结尾很重要，因为只有这样才能避免重复.

这个应该怎么想出来呢？应该从题目中去猜，最终的答案是由什么构成，比如【1，2，3，4，5】
就是由以3结束的等差数组子序列，以4结束的等差数组子序列，以5结束的等差数组子序列
那么就试着去构造，看每个dp【i】能否表示上面所说的情况，然后将各个dp【i】相加就是答案了

然后，找到dp【i】之间的递推关系，如果继续满足等差条件，dp【i】=dp【i-1】+1
为什么呢？比如1 2 3 4 以4结尾的有两个，那么 1 2 3 4 5 应该有2+1个
原本是 1234 234 现在仍然12345 2345 然后多了一个345

最后就找到初始条件，dp【0】，dp【1】为0，i从2开始

        int sum=0;
        int dp[]=new int[nums.length];
        for(int i=2;i<nums.length;i++){
            if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]) dp[i]=dp[i-1]+1;
            sum+=dp[i];
        }
		return sum;

解法二：暴力

        暴力解法
        int sum=0;
        for(int i=0;i<nums.length-3+1;i++){
            int pre=nums[i+1]-nums[i];
            int count=0;
            for(int j=i+1;j<nums.length;j++){
                if(pre!=nums[j]-nums[j-1]) break;
                count++;
                if(count>=2)sum++;
            }
        }
        return sum;