如何优化矩阵中符合条件的':-)'子序列统计代码至线性时间？

需要统计矩阵中符合条件的笑脸:-)数量，要求三个字符分别位于不同行且行号递增、不同列且列号递增。

示例输入矩阵：

7 4
:-)-
\-::- 
)-)-
)-::
\--))
::))
)---

统计结果为10。

当前采用6层嵌套循环实现，结果正确但运行效率极低，代码如下：

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector< vector<char> >Matriu;

int numberSubsequences(const Matriu &m){
int row=m.size();
int column=m[0].size();
int counter=0;


for(int i=0; i<row; ++i){
    for(int j=0; j<column; ++j){
    if(m[i][j]==':'){
        for(int i2=i+1; i2<row; ++i2){
            for(int j2=j+1; j2<column;++j2){
                if(m[i2][j2]=='-'){
                    for(int i3=i2+1; i3<row; ++i3){
                        for(int j3=j2+1; j3<column; ++j3){
                            if(m[i3][j3]==')'){
                                ++counter;
                            }
                        }
                    }
                }
            }
        }
    }
    }
}
    return counter;
    }



int main(){
    int r, c;
    while(cin >> r >> c){
        Matriu m(r,vector<char>(c));
        for(int i=0; i<r; ++i){
            for(int j=0; j<c; ++j){
                cin >> m[i][j];
            }
        }
        cout << numberSubsequences(m) << endl;
    }
}

现寻求优化方案，提升代码运行速度，目标实现接近线性的时间复杂度。

核心思路：预处理+动态规划 #

原代码时间复杂度为O(R³C³)，完全无法处理大矩阵。我们可以通过预处理每个位置的后续符合条件的字符数量，将复杂度降至O(RC)级别。

具体步骤：

1. 预处理每个位置右下方的)数量：创建二维数组count_close，其中count_close[i][j]表示(i,j)右下方（行>i、列>j）所有)的总数，从矩阵右下角往左上角遍历计算。
2. 统计每个-对应的有效)数量：遍历矩阵中的每个-，利用count_close快速获取它能匹配的)数量，存入dash_to_close数组。
3. 统计每个:对应的有效-+)组合数量：预处理得到count_dash_close数组，存储每个位置右下方所有-对应的dash_to_close之和，最后遍历所有:累加对应值得到结果。

优化后的代码 #

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef vector<vector<char>> Matriu;

int numberSubsequences(const Matriu &m) {
    int rows = m.size();
    if (rows == 0) return 0;
    int cols = m[0].size();
    if (cols == 0) return 0;

    // 预处理：count_close[i][j] 表示(i,j)右下方（行>i，列>j）的')'数量
    vector<vector<int>> count_close(rows, vector<int>(cols, 0));
    for (int i = rows - 2; i >= 0; --i) {
        int suffix = 0;
        for (int j = cols - 2; j >= 0; --j) {
            suffix += (m[i][j+1] == ')') ? 1 : 0;
            count_close[i][j] = count_close[i+1][j] + suffix;
        }
    }

    // 统计每个'-'对应的有效')'数量
    vector<vector<int>> dash_to_close(rows, vector<int>(cols, 0));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (m[i][j] == '-') {
                if (i == rows-1 || j == cols-1) {
                    dash_to_close[i][j] = 0;
                } else {
                    dash_to_close[i][j] = count_close[i][j];
                }
            }
        }
    }

    // 预处理：count_dash_close[i][j] 表示(i,j)右下方所有'-'对应的dash_to_close之和
    vector<vector<int>> count_dash_close(rows, vector<int>(cols, 0));
    for (int i = rows - 2; i >= 0; --i) {
        int suffix_sum = 0;
        for (int j = cols - 2; j >= 0; --j) {
            suffix_sum += dash_to_close[i][j+1];
            count_dash_close[i][j] = count_dash_close[i+1][j] + suffix_sum;
        }
    }

    // 统计所有':'对应的有效组合数
    int total = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (m[i][j] == ':') {
                if (i < rows-1 && j < cols-1) {
                    total += count_dash_close[i][j];
                }
            }
        }
    }

    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int r, c;
    while (cin >> r >> c) {
        Matriu m(r, vector<char>(c));
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                cin >> m[i][j];
            }
        }
        cout << numberSubsequences(m) << '\n';
    }
    return 0;
}

复杂度说明 #

所有预处理和统计步骤的时间复杂度均为O(RC)，整体时间复杂度为O(RC)，属于线性级别，可高效处理大规模矩阵。同时代码中加入了ios::sync_with_stdio(false); cin.tie(nullptr);加速输入输出，进一步提升运行效率。

内容的提问来源于stack exchange，提问作者okk