// 演算法同 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());
    }
};