3742. Maximum Path Score in a Grid

// 演算法 / Algorithm:
//   dp[j][c] = 走到目前列、第 j 行,且恰好花成本 c 時的最大分數
//   dp[j][c] = max score upon reaching column j of the current row with exact cost c.
//   逐行 (row-by-row) 滾動更新,讀 dp[j] 拿上一行,讀 dp[j-1] 拿這一行已更新值。
//   We roll row-by-row; dp[j] still holds the previous row, dp[j-1] holds the current row.
//   時間 O(m*n*k),空間 O(n*k) / Time O(m*n*k), space O(n*k).

#include <stdlib.h>  // 提供 malloc / free / provides malloc, free

int maximumPathScore(int** grid, int gridSize, int* gridColSize, int k) {
    int m = gridSize;            // 行數 / number of rows
    int n = gridColSize[0];      // 列數 / number of columns

    // 配置 dp[n][k+1];使用 -1 代表「不可達」/ allocate dp[n][k+1]; -1 means "unreachable"
    int** dp = (int**)malloc(n * sizeof(int*));        // 指標陣列 / array of row pointers
    for (int j = 0; j < n; j++) {                      // 為每一列配置 / allocate each column slice
        dp[j] = (int*)malloc((k + 1) * sizeof(int));   // k+1 個成本桶 / k+1 cost buckets
        for (int c = 0; c <= k; c++) dp[j][c] = -1;    // 初值設為不可達 / mark all unreachable
    }
    dp[0][0] = 0;  // 起點:第 0 列、成本 0、分數 0 / start at column 0, cost 0, score 0

    // 暫存陣列,避免就地寫壞同一行內後面的讀取 / scratch row to avoid clobbering reads
    int* tmp = (int*)malloc((k + 1) * sizeof(int));

    for (int i = 0; i < m; i++) {                      // 由上到下逐行 / iterate rows top-down
        for (int j = 0; j < n; j++) {                  // 由左到右逐列 / iterate columns left-to-right
            if (i == 0 && j == 0) continue;            // 起點已初始化過 / base cell already set
            int v = grid[i][j];                        // 此格的值 0/1/2 / cell value 0, 1, or 2
            int cost = (v != 0) ? 1 : 0;               // 1/2 花費 1,0 不花費 / nonzero cells cost 1
            int score = v;                             // 分數恰好等於 v / score equals the cell value

            for (int c = 0; c <= k; c++) tmp[c] = -1;  // 清空暫存 / clear scratch row

            // c 從 cost 起跳:不到 cost 進不了這格 / start at c=cost: smaller budgets can't enter this cell
            for (int c = cost; c <= k; c++) {
                int prev = c - cost;                   // 進此格前已花的成本 / cost spent before entering
                // 從上面來:dp[j][prev] 還是上一行的值 / "from above" reads previous row at dp[j]
                int from_above = (i > 0 && dp[j][prev] >= 0)
                                    ? dp[j][prev] + score : -1;
                // 從左邊來:dp[j-1][prev] 已是這行更新後的值 / "from left" reads current row at dp[j-1]
                int from_left  = (j > 0 && dp[j-1][prev] >= 0)
                                    ? dp[j-1][prev] + score : -1;
                int best = (from_above > from_left) ? from_above : from_left;  // 取較大 / take the larger
                tmp[c] = best;                          // 寫入暫存 / write into scratch
            }

            for (int c = 0; c <= k; c++) dp[j][c] = tmp[c];  // 把暫存搬回 dp[j] / commit scratch to dp[j]
        }
    }

    int ans = -1;                                      // 預設無解 / default to "no valid path"
    for (int c = 0; c <= k; c++)                       // 在終點掃所有成本 / scan all costs at the goal
        if (dp[n - 1][c] > ans) ans = dp[n - 1][c];    // 取最大分數 / keep the maximum score

    for (int j = 0; j < n; j++) free(dp[j]);           // 釋放每列 / free each column slice
    free(dp);                                          // 釋放指標陣列 / free pointer array
    free(tmp);                                         // 釋放暫存 / free scratch row
    return ans;                                        // 回傳答案;全不可達就是 -1 / return -1 if all unreachable
}

// 演算法同 C 版本:dp[j][c] 為「目前列、第 j 行、成本恰好 c」的最大分數,逐行就地滾動。
// Same algorithm as the C version: dp[j][c] = max score at column j with exact cost c
// in the current row, rolled in place row-by-row.
// Time O(m*n*k), space O(n*k).

#include <vector>      // std::vector 動態陣列 / dynamic array
#include <algorithm>   // std::max, std::max_element, std::fill

class Solution {
public:
    int maximumPathScore(std::vector<std::vector<int>>& grid, int k) {
        int m = grid.size();              // 行數 / row count; vector::size() 回傳元素數 / number of elements
        int n = grid[0].size();           // 列數 / column count

        // 用 vector 配置 n × (k+1) 的 2D 表,初值 -1 / 2D vector of n × (k+1), filled with -1
        std::vector<std::vector<int>> dp(n, std::vector<int>(k + 1, -1));
        dp[0][0] = 0;                     // 起點 / starting cell

        std::vector<int> tmp(k + 1);      // 暫存陣列 / scratch row

        for (int i = 0; i < m; ++i) {                 // ++i 是慣用前置遞增 / idiomatic pre-increment
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;       // 跳過起點 / skip base cell
                int v = grid[i][j];                   // 取值 / read cell value
                int cost  = (v != 0) ? 1 : 0;         // 1/2 成本 1,0 成本 0 / nonzero cells cost 1
                int score = v;                        // 分數即值本身 / score equals value

                std::fill(tmp.begin(), tmp.end(), -1);// 清空暫存 / wipe scratch with -1

                for (int c = cost; c <= k; ++c) {
                    int prev = c - cost;              // 進此格前的成本 / cost before entering
                    int from_above = (i > 0 && dp[j][prev] >= 0)
                                        ? dp[j][prev] + score : -1;   // 上一行同列 / previous row, same column
                    int from_left  = (j > 0 && dp[j-1][prev] >= 0)
                                        ? dp[j-1][prev] + score : -1; // 同行左鄰 / current row, left neighbor
                    tmp[c] = std::max(from_above, from_left);          // 取較大者 / take the larger
                }

                dp[j] = tmp;                          // 整行覆寫;vector 賦值會深拷貝 / assign copies the row
            }
        }

        // max_element 回傳指向最大元素的迭代器,*it 解引用取值
        // max_element returns an iterator to the largest element; * dereferences it
        return *std::max_element(dp[n - 1].begin(), dp[n - 1].end());
    }
};