1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <vector>
#include <cmath>

class Solution {
public:
    long long minCost(int m, int n, std::vector<std::vector<int>>& waitCost) {
        std::vector<long long> dp(n);
        dp[0] = 1;
        
        for (int j = 1; j < n; ++j) {
            dp[j] = dp[j - 1] + j + 1 + waitCost[0][j];
        }
        
        for (int i = 1; i < m; ++i) {
            dp[0] += i + 1 + waitCost[i][0];
            for (int j = 1; j < n; ++j) {
                dp[j] = std::min(dp[j], dp[j - 1]) + (i + 1) * (j + 1) + waitCost[i][j];
            }
        }
        
        return dp.back() - waitCost.back().back();
    }
};