编辑代码

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

#define ROWS 5
#define COLS 6

int collectMaxCoins(int coin[ROWS][COLS]) {
    // 创建一个二维数组dp，用于保存到达每个位置的最大硬币数
    int dp[ROWS][COLS];

    // 初始化dp数组的第一行和第一列
    dp[0][0] = coin[0][0];
    for (int i = 1; i < ROWS; i++) {
        dp[i][0] = dp[i - 1][0] + coin[i][0];
    }
    for (int j = 1; j < COLS; j++) {
        dp[0][j] = dp[0][j - 1] + coin[0][j];
    }

    // 填充dp数组的其余部分
    for (int i = 1; i < ROWS; i++) {
        for (int j = 1; j < COLS; j++) {
            dp[i][j] = coin[i][j] + ((dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]);
        }
    }

    // 打印收集路径
    int i = 0;
    int j = 0;

    printf("收集路径：\n");
    while (i < ROWS - 1 || j < COLS - 1) {
        printf("(%d, %d)\n", i + 1, j + 1);
        if (i < ROWS - 1 && j < COLS - 1) {
            if (dp[i + 1][j] > dp[i][j + 1]) {
                i++;
            } else {
                j++;
            }
        } else if (i < ROWS - 1) {
            i++;
        } else {
            j++;
        }
    }
    printf("(%d, %d)\n", ROWS, COLS);

    // 返回右下角的值，即最大硬币数
    return dp[ROWS - 1][COLS - 1];
}

int main() {
    int coin[ROWS][COLS] = {
            {1, 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, 1, 1, 0}
    };

    int maxCoins = collectMaxCoins(coin);
    printf("收集最大硬币数：%d\n", maxCoins);

    return 0;
}