算法笔记 递推

通过递推关系解题，将可以显著降低时间复杂度。

【PAT B1040】有几个 PAT

解题思路：

直接暴力会导致超时。

研究寻找规律。对于每一个 A ，当它的左边有 P 且右边有 T 时便可以组成 PAT 。而当左边有多个 P ，且右边有多个 T 时，可以组成的集合便是两个集合的笛卡儿积，可以组成的数量是左边的 P 和右边的 T 数量的乘积。即对于一个确定位置的 A ，它可以形成的 PAT 数量等于左边 A 个数和右边 T 个数的乘积。

如何较快地获取每一位左边 P 的个数呢？可以遍历数组，并将左边 P 的数量存储于另一个数组之中。同理， 每一位右边 T 的数量也可以用这个方法很快得到。

然后再遍历一次数组，找到每一个 A ，计算它能够组成的数量，累加至结果即可。（注意取模）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(){
    int i, n, num;
    char str[100010];
    scanf("%s", str);
    n = strlen(str);
    int *p = (int *)calloc(sizeof(int), n);
    int *t = (int *)calloc(sizeof(int), n);
    
    num = 0;
    for (i = 0; i < n; i++){  //统计每一位左边有几个P
        p[i] = num;
        if (str[i] == 'P')    num++;
    }
    num = 0;
    for (i = n - 1; i >= 0; i--){  //统计每一位右边有几个T
        t[i] = num;
        if (str[i] == 'T')    num++;
    }
    num = 0;
    for (i = 0; i < n; i++){
        if (str[i] == 'A'){
            num = (num + p[i] * t[i]) % 1000000007;
        }
    }
    printf("%d", num);
}

​

参考

  • 算法笔记