编辑代码

#include <stdio.h>
#include <stdlib.h>

struct Pair {
    int first;
    int second;
};

int collectCoin(int** coin, int rowCount, int colCount, struct Pair** path) {
    // 1. 构建动态规划表格
    int** dpArray = (int**)malloc((rowCount + 1) * sizeof(int*));
    for (int i = 0; i <= rowCount; ++i) {
        dpArray[i] = (int*)malloc((colCount + 1) * sizeof(int));
    }

    // 2. 填充动态规划表格
    for (int i = 1; i <= rowCount; ++i) {
        for (int j = 1; j <= colCount; ++j) {
            dpArray[i][j] = (dpArray[i - 1][j] > dpArray[i][j - 1]) ? (dpArray[i - 1][j] + coin[i - 1][j - 1]) : (dpArray[i][j - 1] + coin[i - 1][j - 1]);
        }
    }

    // 3. 找到收集路径
    int i = rowCount;
    int j = colCount;
    int pathSize = 0;

    while (i > 0 && j > 0) {
        path[pathSize]->first = i;
        path[pathSize]->second = j;
        pathSize++;

        if (dpArray[i - 1][j] > dpArray[i][j - 1]) {
            i = i - 1;
        } else {
            j = j - 1;
        }
    }

    path[pathSize]->first = 1;
    path[pathSize]->second = 1;
    pathSize++;

    // 反转路径，使其按顺序存储
    for (int k = 0; k < pathSize / 2; k++) {
        struct Pair temp = *path[k];
        *path[k] = *path[pathSize - 1 - k];
        *path[pathSize - 1 - k] = temp;
    }

    // 释放动态分配的内存
    for (int i = 0; i <= rowCount; ++i) {
        free(dpArray[i]);
    }
    free(dpArray);

    return dpArray[rowCount][colCount];
}


void printPath(const struct Pair** path, int pathSize) {
    for (int i = 0; i < pathSize; ++i) {
        printf("(%d,%d)\n", path[i]->first, path[i]->second);
    }
}

int main() {
    int rowCount = 5;
    int colCount = 6;

    int** coin = (int**)malloc(rowCount * sizeof(int*));
    for (int i = 0; i < rowCount; ++i) {
        coin[i] = (int*)malloc(colCount * sizeof(int));
    }

    // 初始化硬币矩阵
    int coinValues[][6] = {
        {0, 0, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 0, 0, 1, 0}
    };

    for (int i = 0; i < rowCount; ++i) {
        for (int j = 0; j < colCount; ++j) {
            coin[i][j] = coinValues[i][j];
        }
    }

    struct Pair** path = (struct Pair**)malloc((rowCount + colCount) * sizeof(struct Pair*));
    for (int i = 0; i < rowCount + colCount; ++i) {
        path[i] = (struct Pair*)malloc(sizeof(struct Pair));
    }

    printf("收集到的硬币数：%d\n", collectCoin(coin, rowCount, colCount, path));
    printPath((const struct Pair**)path, rowCount + colCount);


    // 释放动态分配的内存
    for (int i = 0; i < rowCount; ++i) {
        free(coin[i]);
    }
    free(coin);

    for (int i = 0; i < rowCount + colCount; ++i) {
        free(path[i]);
    }
    free(path);

    return 0;
}