Mdr-C-Tutorial

主题

30806：网格最小路径代价 ​

题目 ​

在只能向右或向下移动的非负代价网格中，求左上角到右下角的最小总代价。

解析 ​

按行处理时，dp[c] 在更新前表示上一行同列的代价，dp[c - 1] 表示当前行左侧代价。第一列只能从上方来，第一行只能从左方来，普通格子取两者较小值。所有加法都在写入状态前检查溢出。

答案 ​

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool minimum_grid_path(
    const uint64_t *costs,
    size_t rows,
    size_t columns,
    uint64_t *out_cost
) {
    if (out_cost == NULL) {
        return false;
    }
    if (rows == 0 || columns == 0) {
        *out_cost = 0;
        return true;
    }
    if (costs == NULL || rows > SIZE_MAX / columns ||
        columns > SIZE_MAX / sizeof(uint64_t)) {
        return false;
    }
    uint64_t *dp = malloc(columns * sizeof *dp);
    if (dp == NULL) {
        return false;
    }
    for (size_t row = 0; row < rows; ++row) {
        for (size_t column = 0; column < columns; ++column) {
            uint64_t cell = costs[row * columns + column];
            if (row == 0 && column == 0) {
                dp[column] = cell;
                continue;
            }
            uint64_t previous = UINT64_MAX;
            if (row > 0) {
                previous = dp[column];
            }
            if (column > 0 && dp[column - 1] < previous) {
                previous = dp[column - 1];
            }
            if (previous > UINT64_MAX - cell) {
                free(dp);
                return false;
            }
            dp[column] = previous + cell;
        }
    }
    *out_cost = dp[columns - 1];
    free(dp);
    return true;
}

时间复杂度为 O(rows×columns)，只保存一行状态，额外空间为 O(columns)。