leetcode413等差数列划分

﹏ヽ暗。殇╰゛Y 2022-09-04 02:50 139阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
思路

1.  `dp[i]`是以`nums[i]`为序列最后一位的等差序列数量
2.  所以最后的所有等差序列数量需要全部累加`dp[i]`
3.  一般求数组数量一维dp就行，不然容易超时

代码

#include<stdio.h>
    #include<string.h>
    int numberOfArithmeticSlices(int* nums, int numsSize){ 
        if(numsSize<=2)
            return 0;
        int dp[numsSize];
        memset(dp,0,sizeof(dp));
        int i;
        for(i=2;i<numsSize;i++){ 
            if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
                dp[i] = dp[i-1]+1;
        }
        int count =0;
        for(i=0;i<numsSize;i++)
            count = count+dp[i];
        return count;
    }

自己写的能找出最长的等差序列，数量的话超时了

#include<stdio.h>
    #include<string.h>
    int numberOfArithmeticSlices(int* nums, int numsSize){ 
        int flag[numsSize][numsSize],i,j;
        memset(flag,0,sizeof(int)*numsSize*numsSize);                               
        for(i=0;i<numsSize;i++){ 
            for(j=0;j<=i;j++){ 
                if(i==j||i-j<2)
                    flag[i][j]=0;
                else if(i-j==2){ 
                    if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
                        flag[j][i]=1;
                }
                else if(i-j>2){ 
                    if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]&&flag[j][i-1])
                        flag[j][i]=1;
                }
            }
        }
    
        int count = 0;
        for(i=0;i<numsSize;i++){ 
            for(j=0;j<=i;j++){ 
                count = count+flag[j][i];
                printf("[%d,%d]=%d ",j,i,flag[j][i]);
            }
            printf("\n");
                
        }
        return count;
    }
    
    int main(){ 
        int num[] = { 1,2,3,4};
        int res = numberOfArithmeticSlices(num,4);
        printf("res = %d\n",res);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/8fe063382c744a65b75576465f66b411.png