编辑代码

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

// 硬币收集问题的函数
int maxCoins(int** grid, int rows, int cols) {
     int dp[rows][cols];
    dp[0][0] = grid[0][0];

    for (int i = 1; i < rows; i++)
        dp[i][0] = dp[i-1][0] + grid[i][0];

    for (int j = 1; j < cols; j++)
        dp[0][j] = dp[0][j-1] + grid[0][j];

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            dp[i][j] = grid[i][j] + (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
        }
    }

    return dp[rows-1][cols-1];
}

// 最大公共字符串子序列问题的函数
int lcs(char* A, char* B) {
   int lenA = strlen(A);
    int lenB = strlen(B);
    int dp[lenA+1][lenB+1];

    for (int i = 0; i <= lenA; i++)
        for (int j = 0; j <= lenB; j++)
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (A[i-1] == B[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

    return dp[lenA][lenB];
}

int main() {
    // 调用硬币收集问题的函数
    int rows = 3, cols = 3;
    int** grid = (int**)malloc(rows * sizeof(int*));
    for(int i = 0; i < rows; i++)
        grid[i] = (int*)malloc(cols * sizeof(int));

    // 填充网格数据
    grid[0][0] = 1; grid[0][1] = 3; grid[0][2] = 1;
    grid[1][0] = 1; grid[1][1] = 5; grid[1][2] = 1;
    grid[2][0] = 4; grid[2][1] = 2; grid[2][2] = 1;

    printf("Max coins collected: %d\n", maxCoins(grid, rows, cols));

    // 释放内存
    for(int i = 0; i < rows; i++)
        free(grid[i]);
    free(grid);

    // 调用最大公共字符串子序列问题的函数
    char A[] = "AGGTAB";
    char B[] = "GXTXAYB";
    printf("Length of LCS: %d\n", lcs(A, B));

    return 0;
}