编辑代码

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

int max(int a, int b) {
    return (a > b) ? a : b;
}

void findMaxCoins(int **board, int n, int m) {
    int **dp = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(m * sizeof(int));
    }

    dp[0][0] = board[0][0];

    // 初始化第一行和第一列
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i-1][0] + board[i][0];
    }
    for (int j = 1; j < m; j++) {
        dp[0][j] = dp[0][j-1] + board[0][j];
    }

    // 填充dp数组
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + board[i][j];
        }
    }

    // 找出最大硬币数和路径
    int maxCoins = dp[n-1][m-1];
    printf("最大硬币数：%d\n", maxCoins);

    // 回溯dp数组找出路径
    int i = n - 1;
    int j = m - 1;
    printf("路径：(%d, %d) ", i, j);
    while (i > 0 || j > 0) {
        if (i == 0) {
            j--;
        } else if (j == 0) {
            i--;
        } else {
            int maxPrev = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
            if (maxPrev == dp[i-1][j-1]) {
                i--;
                j--;
            } else if (maxPrev == dp[i-1][j]) {
                i--;
            } else {
                j--;
            }
        }
        printf("-> (%d, %d) ", i, j);
    }

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

int main() {
    int n = 4;  // 木板的行数
    int m = 5;  // 木板的列数

    int board[4][5] = {
        {1, 3, 1, 2, 1},
        {2, 1, 2, 2, 2},
        {1, 2, 3, 1, 2},
        {1, 1, 1, 2, 1}
    };

    // 将二维数组转换为动态分配的二维数组
    int **dynamicBoard = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        dynamicBoard[i] = (int *)malloc(m * sizeof(int));
        for (int j = 0; j < m; j++) {
            dynamicBoard[i][j] = board[i][j];
        }
    }

    findMaxCoins(dynamicBoard, n, m);

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

    return 0;
}