leetcode 2304. 网格中的最小路径代价

题目如下
数据范围

常规的动态规划题我们可以从上往下遍历 令f(i,j)为从第一行任何一个位置到i,j的代价即可得到转移方程。
f(i,j) = min(f(i - 1,k) + grid[i][j] + moveCost[grid[i - 1][k]][j]) 其中 (0 <= k < m,m为列数)

class Solution {
public:int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {int n = grid.size();int m = grid[0].size();int ans;vector<vector<int>> dp(n, vector<int>(m, 0));for(int i = 0;i < m;i++)dp[0][i] = grid[0][i];for (int i = 1; i < n; i++) {for (int j = 0; j < m; j++) {dp[i][j] = INT_MAX;for (int k = 0; k < m; k++) {dp[i][j] = min(dp[i][j], dp[i - 1][k] + grid[i][j] +moveCost[grid[i - 1][k]][j]);}}}ans = dp[n - 1][0];for (int i = 0; i < m; i++)ans = min(ans, dp[n - 1][i]);return ans;}
};