【十】【C语言\动态规划】376. 摆动序列、673. 最长递增子序列的个数、646. 最长数对链,三道题目深度解析

动态规划

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

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

数学归纳法:

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

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

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

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

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

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

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

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

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

376. 摆动序列 - 力扣(LeetCode)

题目解析

状态表示

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

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

我们可以很容易定义这样一个状态表示,定义dp[i]表示以i位置元素为结尾的子序列中,最长的摆动序列长度。

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

dp[i]表示以i位置元素为结尾的子序列中,最长的摆动序列长度。

我们针对于(以i位置元素为结尾的子序列,以及i位置元素状态)进行分析,想一想dp[i]能不能由其他状态推导得出。

  1. 如果只考虑i位置一个元素, 最长的摆动序列长度为1,故dp[i]=1。

  2. 如果不止考虑i位置一个元素, 我们发现还需要考虑i位置元素处于“上升”状态还是“下降”状态

    1. 如果i位置元素处于“上升”状态,i位置元素可以跟在前面任意(nums[j]<nums[i])的元素后面,我们假设i位置元素跟着j位置元素后面,j位置元素需要处于“下降”状态,而我们要考虑的是最长的摆动序列长度,所以j需要遍历(0~i-1),dp[i]=max(j位置元素(处于”下降“状态,最长的摆动序列长度)+1)j∈[0~i-1]。

    2. 如果i位置元素处于“下降”状态,i位置元素可以跟在前面任意(nums[j]>nums[i])的元素后面,我们假设i位置元素跟着j位置元素后面,j位置元素需要处于“上升”状态,而我们要考虑的是最长的摆动序列长度,所以j需要遍历(0~i-1),dp[i]=max(j位置元素(处于”上升“状态,最长的摆动序列长度)+1)j∈[0~i-1]。

我们发现只定义(dp[i]表示以i位置元素为结尾的子序列中,最长的摆动序列长度)这个状态表示是没办法推导出状态转移方程,所以我们修正一下状态表示。

定义 ,

f[i]表示以i位置元素为结尾的子序列中,处于“上升”状态时,最长的摆动序列长度。

g[i]表示以i位置元素为结尾的子序列中,处于“下降”状态时,最长的摆动序列长度。

状态转移方程

我们针对于(以i位置元素为结尾的子序列,以及i位置元素状态)进行分析,想一想dp[i]能不能由其他状态推导得出。

  1. 如果只考虑i位置一个元素, 最长的摆动序列长度为1,故f[i]=g[i]=1。

  2. 如果不止考虑i位置一个元素, 我们发现还需要考虑i位置元素处于“上升”状态还是“下降”状态

    1. 如果i位置元素处于“上升”状态,i位置元素可以跟在前面任意(nums[j]<nums[i])的元素后面,我们假设i位置元素跟着j位置元素后面,j位置元素需要处于“下降”状态,而我们要考虑的是最长的摆动序列长度,所以j需要遍历(0~i-1),f[i]=max(g[j]+1)j∈[0~i-1],g[i]=1。

    2. 如果i位置元素处于“下降”状态,i位置元素可以跟在前面任意(nums[j]>nums[i])的元素后面,我们假设i位置元素跟着j位置元素后面,j位置元素需要处于“上升”状态,而我们要考虑的是最长的摆动序列长度,所以j需要遍历(0~i-1),g[i]=max(f[i]+1)j∈[0~i-1],f[i]=1。

将上述情况进行简化和合并,我们发现有许多情况f[i]=g[i]=1,并且1是最低的标准,任何位置的状态最少都是1,所以我们可以把这些情况放在初始化部分处理,即先把所有位置的状态初始化为1。

所以我们可以得到状态转移方程,

 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                f[i] = fmax(f[i], g[j] + 1);
            } else if (nums[i] < nums[j]) {
                g[i] = fmax(g[i], f[j] + 1);
            }
        }
    }

初始化

根据状态转移方程,我们推导i位置的状态时,需要用到(0~i-1)位置的状态,所以我们应该初始化第一个位置的状态,即f[0]=g[0]=1。

结合状态转移方程中的分析,所有位置的状态都需要初始化为1,所以我们统一初始化状态为1。即,

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

填表顺序

根据状态转移方程,我们推导i位置的状态时,需要用到(0~i-1)位置的状态,所以我们应该从左往右填表,即,

从左往右。

返回值

f[i]表示以i位置元素为结尾的子序列中,处于“上升”状态时,最长的摆动序列长度。

g[i]表示以i位置元素为结尾的子序列中,处于“下降”状态时,最长的摆动序列长度。

结合题目意思,我们需要找到最长的摆动序列长度,所以我们应该遍历f,g数组找到最长的长度然后返回。

代码实现

 

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

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

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                f[i] = fmax(f[i], g[j] + 1);
            } else if (nums[i] < nums[j]) {
                g[i] = fmax(g[i], f[j] + 1);
            }
        }
        ret = fmax(ret, fmax(f[i], g[i]));
    }
    return ret;
}

673. 最长递增子序列的个数 - 力扣(LeetCode)

题目解析

状态表示

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

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

我们可以很容易定义这样一个状态表示,定义dp[i]表示以i位置元素为结尾的子序列中,最长的严格递增序列的个数。

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

dp[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的个数。

我们想要由其他位置的状态推导出i位置的状态,只知道最长的严格递增子序列个数是不够的,因为我不知道你对应的最长子序列的长度。

所以我们还需要一个状态记录对应的最长子序列的长度。

定义,

len[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的长度。

count[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的个数。

状态转移方程

len[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的长度。

count[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的个数。

我们针对于(以i位置元素为结尾的子序列,以及i位置元素状态)进行分析,想一想dp[i]能不能由其他状态推导得出。

  1. 如果只考虑i位置一个元素, len[i]=1,count[i]=1;

  2. 如果不止考虑i位置一个元素, 我们考虑的是子序列,i位置元素可能跟在前面任意(nums[i]>nums[j])元素后面,因此我们用j表示(0~i-1)区间上的下标。

    1. 在求个数之前,我们得知道长度,因此先看len[i],

          综上所述,对于len[i],我们可以得到状态转移方程, len[i]=max(len[i],len[j]+1),其中(0<=j<i),并且nums[i]>nums[j]。

      1. 在求i位置的len时,我们已经知道(0,i-1)位置上的len信息。

      2. 我们需要的是递增序列,因此nums[i]只要能和nums[j]构成上升序列,那就可以更新len[i]的值,此时最长的长度为len[j]+1。

      3. 我们要的是(0~i-1)区间上所有情况下的最大值。

    2. 在知道每个位置为结尾的最长递增子序列的长度时,我们尝试推导count状态。

          综上所述,对于count[i],我们可以得到状态转移方程,

          count[i]+=count[j],其中(0<=j<i),并且nums[j]<nums[i]&&(len[j]+1==len[i])。

      1. 我们现在已经知道len[i]的信息,以及(0~i-1)位置上count[j]的信息。

      2. 我们再遍历(0~i-1)只要能构成上升序列,并且上升序列的长度为len[i],那么就可以把count[i]加上count[j]的值。这样循环一遍后,count[i]就是我们想要的值。

将上述情况简化和合并,

我们可以先填写len状态再填写count状态,状态转移方程为,

 
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j] && len[j] + 1 > len[i])
                len[i] = len[j] + 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j] && len[j] + 1 == len[i])
                count[i] += count[j];

        count[i] = fmax(count[i], 1);
    }

初始化

根据状态转移方程,我们推导i位置的状态时,需要用到(0~i-1)位置的状态,所以我们应该初始化第一个位置的状态,即len[0]=count[0]=1。

根据状态转移方程,在填写len状态时,我们先考虑(如果不止考虑i位置一个元素,)这种情况,如果i位置元素可以和(0~i-1)位置的元素构成上升序列,那么len[i]就可以由len[j]推导得出,如果(0~i-1)位置上没有一个j可以构成上升序列,再考虑(如果只考虑i位置一个元素)这种情况,len[j]就等于1。

因为len状态的推导是赋值,所以我们可以将所有位置上len状态初始化为1。

在填写count状态时,我们先考虑(如果不止考虑i位置一个元素,)这种情况,在(0~i-1)中记录最长递增子序列的个数,所以count[i]应该初始化为0。再考虑(如果只考虑i位置一个元素)这种情况,count[i]=max(count[i],1)。

综上所述,初始化为,

 
    for (int i = 0; i < n; i++) {
        len[i] = 1;
        count[i] = 0;
    }
    count[0] = 1;

填表顺序

根据状态转移方程,我们推导i位置的状态时,需要用到(0~i-1)位置的状态,所以我们应该从左往右填写。即,

从左往右。

返回值

len[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的长度。

count[i]表示以i位置元素为结尾的子序列中,最长的严格递增子序列的个数。

结合题目意思,我们应该返回最长递增子序列的个数,所以我们需要遍历len找到最长递增子序列的长度,然后遍历count统计最长子序列的个数,然后返回。

代码实现

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

    int len[n], count[n];
    for (int i = 0; i < n; i++) {
        len[i] = 1;
        count[i] = 0;
    }
    count[0] = 1;
    int retlen = 1;
    int retcount = 0;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j] && len[j] + 1 > len[i])
                len[i] = len[j] + 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j] && len[j] + 1 == len[i])
                count[i] += count[j];

        count[i] = fmax(count[i], 1);
    }

    for (int i = 0; i < n; i++)
        retlen = fmax(retlen, len[i]);

    for (int i = 0; i < n; i++)
        if (len[i] == retlen)
            retcount += count[i];

    return retcount;
}

retcount += count[i]; return retcount; }

646. 最长数对链 - 力扣(LeetCode)

题目解析

状态表示

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

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

我们可以很容易定义这样一个状态表示,定义dp[i]表示以i位置数对为结尾的子序列中,最长递增数对链的长度。

状态转移方程

dp[i]表示以i位置数对为结尾的子序列中,最长递增数对链的长度。

我们针对于(以i位置数对为结尾的子序列,以及i位置数对状态)进行分析,想一想dp[i]能不能由其他状态推导得出。

  1. 如果只考虑i位置一个数对, dp[i]=1。

  2. 如果不止考虑i位置一个数对, i位置的数对可能跟在前面满足(pairs[i][0]>pairs[j][1])的任意数对后面,用j表示(0~i-1)中间的某个数。 如果(pairs[i][0]>pairs[j][1])i位置数对第一个元素可以与j位置第二个元素构成上升序列,此时递增数对链的长度为dp[j]+1。 而(0<=j<=i-1),dp[i]存储的是最长递增数对链的长度。 所以dp[i]=max(dp[i],dp[j]+1),0<=j<=i-1。

将上述情况进行合并和简化,dp[i]=max(如果只考虑i位置一个数对,如果不止考虑i位置一个数对),(如果不止考虑i位置一个数对)这种情况中,取max时,需要在自己和前面的值进行选择,前面的值已经得到,所以自己应该要初始化。又因为是对dp[i]进行赋值操作,所以如果这种情况可以进行赋值,那么初始化的值就不会对这种情况有影响。如果这种情况不存在,dp[i]存储的值就是初始化的值。结合(如果只考虑i位置一个数对)这种情况,如果第二种情况不存在,dp[i]应该存储1。

所以我们可以将所有位置的状态初始化为1,这样就可以只考虑第二种情况,

状态转移方程可以简化为,

 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[i][0] > pairs[j][1]) {
                dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
    }

初始化

根据状态转移方程,推导i位置的状态时,需要用到(0~i-1)位置的状态,所以我们需要初始化第一个位置的状态,即,dp[0]=1。结合状态转移方程的分析,我们需要把所有状态初始化为1。结合可以得到初始化,

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

填表顺序

根据状态转移方程,推导i位置的状态时,需要用到(0~i-1)位置的状态,所有我们应该从左往右填写,保证推导i位置状态时,(0~i-1)位置的状态已经得到。

返回值

dp[i]表示以i位置数对为结尾的子序列中,最长递增数对链的长度。

结合题目意思,我们需要在排列后的所有子序列中找到最长递增数对链的长度,所以我们需要遍历dp数组找到最长递增数对链的长度。

代码实现

 
static inline int cmp(const void *pa, const void *pb) {
    if ((*(int **)pa)[0] == (*(int **)pb)[0]) {
        return (*(int **)pa)[1] == (*(int **)pb)[1];
    } 
    return (*(int **)pa)[0] - (*(int **)pb)[0];
}
int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) {
    int n = pairsSize;
    int dp[n];
    qsort(pairs,pairsSize,sizeof(int *),cmp);

    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }
    int ret = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[i][0] > pairs[j][1]) {
                dp[i] = fmax(dp[i], dp[j] + 1);
            }
        }
        ret = fmax(ret, dp[i]);
    }

    return ret;
}

结尾

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

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

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

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