【八】【C语言\动态规划】1567. 乘积为正数的最长子数组长度、413. 等差数列划分、978. 最长湍流子数组,三道题目深度解析

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

1567. 乘积为正数的最长子数组长度

题目解析

状态表示

状态表示一般通过经验+题目得到。

经验一般指以某个位置为结尾或者以某个位置为开始。

我们很容易可以定义这样一个dp状态表示,dp[i]表示以下标i为结尾的所有子数组中,乘积为正数的最长子数组长度。

我们可以尝试推导一下该状态表示的状态转移方程。

dp[i]表示以下标i为结尾的所有子数组中,乘积为正数的最长子数组长度。

我们关注所有以下标i为结尾的子数组,可以分为两种情况,第一种情况是子数组只有下标i一个元素,第二种情况是子数组不止下标i一个元素。

第一种情况,如果nums[i]>0,dp[i]=1,否则dp[i]=0。

第二种情况,我们可以将i下标元素单独分开,看成两部分。

如果nums[i]>0,dp[i]=dp[i-1]+1。

如果nums[i]=0,dp[i]=0。

如果nums[i]<0,dp[i]=(在第一部分所有子数组中,乘积为负数的最长子数组长度)+1。

我们发现还需要一个状态才能填写dp状态。所以我们应该添加一个状态,表示以下标i为结尾的所有子数组中,乘积为负数的最长子数组长度。

因此我们可以重新定义状态表示,

f[i]表示以下标i为结尾的所有子数组中,乘积为正数的最长子数组长度。

g[i]表示以下标i为结尾的所有子数组中,乘积为负数的最长子数组长度。

状态转移方程

根据上面的分析,可以分一下这些情况

  1. 如果只考虑i一个元素,

    • nums[i]>0时,f[i]=1,g[i]=0

    • nums[i]<0时,f[i]=0,g[i]=1

    • nums[i]=0时,f[i]=0,g[i]=0

  2. 如果不止考虑i一个元素,

    1. nums[i]>0时,考虑两种情况

      1. 第一种情况,f[i-1]=0,此时f[i]=0,因为我们考虑不止一个元素,所以最少是两个元素,子数组乘积一定是零,所以长度为0。 g[i-1]=0,此时g[i]=0,同理。

      2. 第二种情况,f[i-1]!=0,此时f[i]=f[i-1]+1,g[i]=g[i-1]+1。第一部分乘积为正数的最长子数组,后面添加nums[i]这个元素,乘积是正数乘以正数,是正数,所以f[i]=f[i-1]+1。 第一部分乘积为负数的最长子数组,后面添加nums[i]这个元素,乘积是负数乘以正数,是负数,所以g[i]=g[i-1]+1。

    2. nums[i]<0时,同样考虑两种情况

      1. 第一种情况,f[i-1]=0,此时f[i]=0,因为我们考虑不止一个元素,所以最少是两个元素,子数组乘积一定是零,所以长度为0。 g[i-1]=0,此时g[i]=0,同理。

      2. 第二种情况,f[i-1]!=0,此时f[i]=g[i-1]+1,g[i]=f[i-1]+1。第一部分乘积为负数的最长子数组,后面添加nums[i]这个元素,乘积是负数乘以负数,是正数,所以f[i]=g[i-1]+1。 第一部分乘积为正数的最长子数组,后面添加nums[i]这个元素,乘积是正数乘以负数,是负数,所以g[i]=f[i-1]+1。

    3. nums[i]=0时,f[i]=0,g[i]=0

我们可以整理一下上述情况,看看哪些情况是可以合并在一起的。

f[i]=max(如果只考虑i一个元素,如果不止考虑i一个元素)

g[i]=max(如果只考虑i一个元素,如果不止考虑i一个元素)

最终我们可以合并成这样,

 
        if(nums[i]==0) f[i]=g[i]=0;
        else if(nums[i]>0){
            f[i]=f[i-1]+1;
            g[i]=g[i-1]==0?0:g[i-1]+1;
        }else{
            f[i]=g[i-1]==0?0:g[i-1]+1;
            g[i]=f[i-1]+1;

        }

上述即状态转移方程。

初始化

根据状态转移方程我们知道,想要推导出i位置的状态,需要用到i-1位置的状态,所以我们需要初始化第一个状态,即f[0]、g[0]

 
    f[0]=nums[0]>0?1:0;
    g[0]=nums[0]<0?1:0;

填表顺序

根据状态转移方程我们知道,想要推导出i位置的状态,需要用到i-1位置的状态,所以我们应该从左往右填写,保证推导i位置状态时,i-1位置状态已经得到。

从左往右填写。

返回值

f[i]表示以下标i为结尾的所有子数组中,乘积为正数的最长子数组长度。

g[i]表示以下标i为结尾的所有子数组中,乘积为负数的最长子数组长度。

结合题目意思,我们应该遍历f数组中所有元素,记录最大的状态值,然后返回。

代码实现

 
int getMaxLen(int* nums, int numsSize){
    int n=numsSize;

    int f[n],g[n];
    f[0]=nums[0]>0?1:0;
    g[0]=nums[0]<0?1:0;

    int ret=nums[0]>0?1:0;
    for(int i=1;i<n;i++){
        if(nums[i]==0) f[i]=g[i]=0;
        else if(nums[i]>0){
            f[i]=f[i-1]+1;
            g[i]=g[i-1]==0?0:g[i-1]+1;
        }else{
            f[i]=g[i-1]==0?0:g[i-1]+1;
            g[i]=f[i-1]+1;

        }

        ret=fmax(ret,f[i]);

    }
    return ret;
}

413. 等差数列划分

题目解析

状态表示

状态表示一般由经验+题目得到

经验一般是,以某个位置为结尾,或者以某个位置为开始。

我们很容易可以定义这样一个dp状态表示,dp[i]表示以下标i为结尾的所有子数组中,是等差数组的子数组个数。

状态转移方程

dp[i]表示以下标i为结尾的所有子数组中,是等差数组的子数组个数。

对于 dp[i] 位置的元素 nums[i] ,会与前面的两个元素有下面两种情况:

  1. nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列:那么以nums[i] 为结尾的等差数列就不存在,此时 dp[i] = 0 ;

  2. nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列:那么以nums[i - 1] 为结尾的所有等差数列后面填上一个 nums[i] 也是一个等差数列,此时dp[i] = dp[i - 1] 。但是,因为nums[i - 2], nums[i - 1], nums[i] 三者又能构成一个新的等差数列,因此要在之前的基础上再添上一个等差数列,于是dp[i] = dp[i - 1] + 1 。

综上所述:状态转移方程为:

当: nums[i - 2] + nums[i] != 2 * nums[i - 1] 时, dp[i] = 0

当: nums[i - 2] + nums[i] == 2 * nums[i - 1] 时, dp[i] = 1 + dp[i - 1]

初始化

根据状态转移方程,我们知道,想要推导出i位置的状态,需要用到i-1,i-2位置的状态,所以我们需要初始化前两个位置的状态。

根据状态表示,dp[i]表示以下标i为结尾的所有子数组中,是等差数组的子数组个数。

很容易得到,

dp[0]=0

dp[1]=0

因为等差数组最少要有三个元素。

填表顺序

根据状态转移方程,我们知道,想要推导出i位置的状态,需要用到i-1,i-2位置的状态,所以我们推导i位置的状态时,i-1和i-2位置的状态应该已经得出。

所以填表顺序应该为,

从左往右。

返回值

根据状态表示,dp[i]表示以下标i为结尾的所有子数组中,是等差数组的子数组个数。

结合题目意思,我们应该遍历dp数组,统计以每个元素为结尾的等差子数组的个数。

代码实现

 

int numberOfArithmeticSlices(int* nums, int numsSize){
    int n=numsSize;
    if(n==1||n==2) return 0;
    int dp[n];
    dp[0]=0;
    dp[1]=0;
    int count=0;
    for(int i=2;i<n;i++){
        if(nums[i - 2] + nums[i] != 2 * nums[i - 1]) dp[i] = 0 ;
        else dp[i] = 1 + dp[i - 1];
        count+=dp[i];
    }

    return count;
}

978. 最长湍流子数组

题目解析

所谓湍流子数组,就是子数组中,每相邻的两个数呈现一上一下状态,交替出现。

状态表示

状态表示一般由经验+题目得到

经验一般是,以某个位置为结尾,或者以某个位置为开始。

子数组的求解,我们一般都可以以某个位置为结尾解决状态表示。

我们很容易可以定义这样一个dp状态表示,dp[i]表示以下标i为结尾的所有子数组中,最长湍流子数组的长度。

我们可以尝试推导一下该状态表示的状态转移方程。

dp[i]表示以下标i为结尾的所有子数组中,最长湍流子数组的长度。

我们想要通过dp[i-1]推导出dp[i],首先需要判断nums[i]和nums[i-1]的大小以及dp[i-1]表示的最长湍流子数组中,nums[i-1]处于“上升”状态还是“下降”状态。因此我们应该存储i元素处于“上升”还是“下降”状态。

我们可以重新定义状态表示,

f[i]表示以下标i为结尾的所有子数组中,i元素处于“上升”状态时,湍流子数组最长的长度。

g[i]表示以下标i为结尾的所有子数组中,i元素处于“下降”状态时,湍流子数组最长的长度。

状态转移方程

  1. 如果只考虑i唯一一个元素,f[i]=g[i]=1,最小的湍流子数组长度就是1。

  2. 如果不止考虑i一个元素,

    1. 如果nums[i]>nums[i-1],f[i]=g[i-1]+1,g[i]=1

    2. 如果nums[i]<nums[i-1],f[i]=1,g[i]=f[i-1]+1

    3. 如果nums[i]=nums[i-1],f[i]=g[i]=1

有很多情况,f[i],g[i]的值是1,我们可以初始化,把所有的数据初始化为1,把这些情况放到初始化里面解决。

所有我们只需要考虑剩下的情况,

得到状态转移方程为,

 
        if(arr[i]>arr[i-1]) f[i]=g[i-1]+1;
        else if(arr[i]<arr[i-1])g[i]=f[i-1]+1;

初始化

根据状态转移方程,我们知道,想要推导出i位置的状态,需要用到i-1位置的状态,

所以我们需要初始化第一个位置的状态。

同时在状态转移方程推导时,我们将许多情况放到初始化阶段来解决,所以我们同时应该初始化所有数据为1。

如果只考虑第一个位置,我发现f[0]=g[0]=1。

所以我们只需要把所有数据初始化为1即可。

填表顺序

根据状态转移方程,我们知道,想要推导出i位置的状态,需要用到i-1位置的状态,

所以我们在推导i位置的状态时,应该已经得到i-1位置的状态。

所以我们应该从左往右填写,一次填写两个表。

返回值

f[i]表示以下标i为结尾的所有子数组中,i元素处于“上升”状态时,湍流子数组最长的长度。

g[i]表示以下标i为结尾的所有子数组中,i元素处于“下降”状态时,湍流子数组最长的长度。

结合题意,我们应该遍历f数组,记录最大的湍流子数组长度。

代码实现

 
int maxTurbulenceSize(int* arr, int arrSize) {
    int n=arrSize;

    int f[n],g[n];
    for(int i=0;i<n;i++){
        f[i]=1;
        g[i]=1;
    }

    int ret=1;
    for(int i=1;i<n;i++){
        if(arr[i]>arr[i-1]) f[i]=g[i-1]+1;
        else if(arr[i]<arr[i-1])g[i]=f[i-1]+1;

        ret=fmax(ret,fmax(f[i],g[i]));
    }
    return ret;
}

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!