2304. 网格中的最小路径代价-297地平线周赛回顾

 有一说一，如果这道题用dfs不会报超时错误的话，对我来说还是比较简单的，但事与愿违，dfs确实不好做这道题，计算量太大，很容易超时。

当然，凡是能用dfs做的且超时，用dp做基本都能解，可能我个人对dp不是很熟练，所以写起来有点磕磕绊绊。

思路：

dp数组的意义还是很好理解的，就是第1行到 第 i 行 第 j 列所用的最小代价。

ps：这里难就难在路径太多，数值太多，让人有点晕- -

动规五部曲：

1.dp数组---含义见上；

2.初始化----显然第一行到自己这一行的代价是它本身；

3.递推公式：重点！！！

dp[i][j]----表示到 第 i 行 第 j 列的最小值；则该值由两个方向可以得到，一个是选择当前节点作为路径节点加入到路径中，另一个就是不选择当且节点为路径节点，而是沿用之前选择过的结点。两者作比较，选择最小的。

dp[i][j]=min(dp[i][j],dp[i-1][j]+moveCost[grid[i-1][k]][j]+grid[i][j]);

 注意：此时有三层循环 i j 表示当前 行列，k代表上一轮选择的列

class Solution {
public:
int res=INT_MAX;
int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
	//dp[i][j] 数组的含义：第一行 到 第 i 行 第 j 列花费的最小代价
	vector<vector<int>>dp(grid.size(),vector<int>(grid[0].size(),INT_MAX));
	//初始化
	for (int j = 0; j < grid[0].size(); j++)dp[0][j] = grid[0][j];
	//递推公式
	//dp[i][j] = min(dp[i][j], dp[i-1][j] +moveCost[grid[i-1][j]][j]);
	//遍历顺序 从前到后
	for (int i = 1; i < grid.size(); i++)
	{
		for (int j = 0; j < grid[i].size(); j++)  //表示 一个结点
		{
			for (int k = 0; k < grid[i].size(); k++) //表示结点所在列
			{
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j]);
			}
		}
	}
	for (int j = 0; j < grid[0].size(); j++)
		res = min(res, dp[grid.size() - 1][j]);
	return res;
	//打印dp
}
};

————————————————此处可不看————————————————————— 

也让我沾一下我的dfs吧，花了老鼻子劲写的，除了数据大跑不动以外，小数据量还是对的，让它见见外面的世界 ~

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int result_1 = 0;
int result_2 = 0;
int result;
int minnum = INT_MAX;
void dfs(vector<vector<int>>& grid, vector<vector<int>>& moveCost, int p_val, vector<int>& v, int x, int y)
{   
    if (x == grid.size() - 1&&v.size()==grid.size())
    {
        result = result_1 + result_2;
        minnum = minnum > result ? result : minnum;
        return;
    }
    for (int i = x + 1; i < grid.size(); i++){
        for (int j = 0; j < grid[0].size(); j++)
        {
            result_1 += moveCost[p_val][j];
            result_2 += grid[i][j];
            v.push_back(p_val);
            dfs(grid, moveCost, grid[i][j], v, i, j);
            v.pop_back();
           // result -= (grid[i][j]+ moveCost[p_val][j]);
            result_2 -= grid[i][j];
            result_1 -= moveCost[p_val][j];
        }
    }
    return;
}
int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
    vector<int>v;
    for (int i = 0; i < grid[0].size(); i++)
    {     
        result_2 += grid[0][i];
        v.push_back(grid[0][i]);
        dfs(grid, moveCost, grid[0][i], v, 0, i);
        v.pop_back();
        result_2 -= grid[0][i];
    }
    return minnum;
}
int main()
{
	int g_row, g_col, c_row, c_col;
	cin >> g_row >> g_col >> c_row >> c_col;
	vector<vector<int>>grid(g_row, vector<int>(g_col, 0));
	vector<vector<int>>moveCost(c_row, vector<int>(c_col, 0));
	for (int i = 0; i < g_row; i++)
	{
		for (int j = 0; j < g_col; j++)
		{
			cin >> grid[i][j];
		}
	}
	for (int i = 0; i < c_row; i++)
	{
		for (int j = 0; j < c_col; j++)
		{
			cin >> moveCost[i][j];
		}
	}
	minPathCost(grid, moveCost);
    cout << minnum;
	return 0;

动规得努力啊！！！！