C语言 等差数列划分 动态规划解法

• • 题目
  • 代码I（动态规划）
  • 分析：
  • 代码II（动态规划优化）
  • 其他解法
  • 代码III（其他解法）

给定一个数组，求数组中所有未等差数组的子数组个数。子数组是数组中连续的序列

int numberOfArithmeticSlices(int* nums, int numsSize){
    if(numsSize<=2){
        return 0;
    }
    int dp[numsSize];
    memset(dp,0,sizeof(dp));
    int sum = 0;
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2;i < numsSize;i++){
        if(2*nums[i-1] == nums[i-2]+nums[i]){
            dp[i] = dp[i-1] + 1;
        }else{
            dp[i] = 0;
        }
        sum += dp[i];
    }
    return sum;
}

dp[i]表示以第i个元素结尾的等差子数组个数,并且声明一个最终返回的变量sum表示个数。dp[0] = 0,dp[1] = 0。接下来找状态转移方程。对于dp[i]来说如果它满足nums[i]-nums[i-1] = nums[i-1]-nums[i-2]那么就说明该等差数列可以和dp[i-1]相连成一个等差数列。即dp[i] = dp[i-1]+1.为什么这里是加1呢？我们以[1,2,3,4,5]为例，dp[0] = dp[1] = 0。dp[2] = 1，dp[3] = 2.首先dp[i-1]的值如果是k，那么对于dp[i]来说每一种对应的子数组后面都可以加上一个Nums[i]，除此之外，因为多了一个元素，就多了一个子数组。比如dp[4],我们已经求出来dp[3] = 2的分别对应[1,2,3,4],[2,3,4]那么对于dp[4]肯定有[1,2,3,4,5],[2,3,4,5]那么除此之外还会多一个[3,4,5]解。如果不满足nums[i]-nums[i-1] = nums[i-1] -nums[i-2],说明以该元素结尾的子数组个数为0.dp[i] = 0。同时每次求出来新的dp[i]，就与sum累加。最终返回sum。又因为本题只与dp[i]只和dp[i-1]有关。我们可以定义一个k变量表示以当前元素为结尾的子数组个数代码如下：

int numberOfArithmeticSlices(int* nums, int numsSize){
    if(numsSize<=2){
        return 0;
    }
    int sum = 0;
    int k = 0;
    for(int i = 2;i < numsSize;i++){
        if(2*nums[i-1]==nums[i]+nums[i-2]){
            k = k + 1;
        }else{
            k = 0;
        }
        sum+=k;
    }
    return sum;
}

当然本题出了动态规划的解法，还有其他解法。利用两层循环，第一层表示子数组的首元素，逐个往后便利，如果符合等差条件，就计数+1，如果不满足，就跳出二层循环，将首元素后移一位，直到到倒数第三个元素截至。

int numberOfArithmeticSlices(int* nums, int numsSize){
    int ans = 0;
    for(int i = 0;i <= numsSize-3;i++){
        for(int j = i + 2;j < numsSize;j++){
            if(2*nums[j-1] == nums[j-2]+nums[j]){
                ans++;
            }else{
                break;
            }
        }
    }
    return ans;
}