编辑代码

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

#define R 100
#define L 100

// 定义木板上每个单元格的硬币数量
int map[R][L] = {
    {0, 1, 0, 1, 0, 1, 1},
    {1, 0, 1, 0, 1, 0, 0},
    {0, 0, 1, 0, 1, 0, 1},
    {0, 1, 0, 1, 0, 0, 1}, 
    {0, 1, 0, 1, 0, 1, 1},
    {1, 0, 1, 0, 1, 0, 0},
    {1, 0, 1, 0, 1, 0, 1},
};

// 定义动态规划数组，存储到达每个单元格的最大硬币数
int table[R][L];
// 定义保存路径的数组
int p[R][L];
int maxCoins(int row, int colum) {
    table[0][0] = map[0][0];
    p[0][0] = -1; 
    // 初始化
    for (int i = 1; i < row; i++) {
        table[i][0] = table[i - 1][0] + map[i][0];
        p[i][0] = 0; // 表示从上方过来
    }
    for (int j = 1; j < colum; j++) {
        table[0][j] = table[0][j - 1] + map[0][j];
        p[0][j] = 1; // 表示从左侧过来
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < colum; j++) {
            if (table[i - 1][j] > table[i][j - 1]) {
                table[i][j] = table[i - 1][j] + map[i][j];
                p[i][j] = 0; // 表示从上方过来
            } else {
                table[i][j] = table[i][j - 1] + map[i][j];
                p[i][j] = 1; // 表示从左侧过来
            }
        }
    }
    // 输出路径
    int i = row - 1;
    int j = colum - 1;
    printf("路径: (%d, %d) ", i, j);
    while (p[i][j] != -1) {
        if (p[i][j] == 0) {
            i--;
        } else {
            j--;
        }
        printf("-> (%d, %d) ", i, j);
    }
    printf("\n");

    // 返回最大硬币数
    return table[row - 1][colum - 1];
}

int main() {
    int row = 7; // 木板的行数
    int colum = 7; // 木板的列数
    // 计算最大硬币数并输出路径
    int result = maxCoins(row, colum);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    result = maxCoins(6, 5);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    result = maxCoins(5, 4);
    // 输出最大硬币数
    printf("硬币数: %d\n", result);

    return 0;
}