【算法刷题】—7.30DP动态规划的应用

【算法刷题】—7.30DP动态规划的应用 2022-08-01 962

🧛♂️个人主页： 💡进步是今天的活动，明天的保证！ ✨目前正在学习：, 👉本文收录专栏： 🙌牛客网，刷算法过面试的神级网站，用牛客你也牛。 👉👈 🐳希望大家多多支持🥰一起进步呀！ 😎The man who fears losing has already lost. 怕输的人已经输了。 - 《权力的游戏》

✨今日算法一题

网格中的最小路径代价

题目描述

思路详解

我们仔细观察题目，这是一道典型的dp题目。定义状态：dp[i][j]表示以gril[i][j]结尾的路径的的最小值状态转移：dp[i][j] = Math.min(dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j],dp[i][j]); dp[i - 1][k] 从dp[i-1][k]到dp[i][j] moveCost[grid[i - 1][k]][j] 从dp[i-1][k]到dp[i][j]的路径的值 grid[i][j] 该点的值

代码与结果

class Solution {
          
   
    public int minPathCost(int[][] grid, int[][] moveCost) {
          
   
		int n = grid.length, m = grid[0].length;
		int[][] dp = new int[n][m];//dp[i][j]表示以gril[i][j]结尾的路径的最小值
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < dp.length; i++) {
          
   
			Arrays.fill(dp[i], Integer.MAX_VALUE);
		}
		for (int j = 0; j < m; j++) {
          
   
			dp[0][j] = grid[0][j];
		}
		for (int i = 1; i < n; i++) {
          
   
			for (int j = 0; j < m; j++) {
          
   
				for (int k = 0; k < m; k++) {
          
   
					/*
					 * dp[i - 1][k] 从dp[i-1][k]到dp[i][j]
					 * moveCost[grid[i - 1][k]][j] 从dp[i-1][k]到dp[i][j]的路径的值
					 * grid[i][j]  该点的值
					 */
					dp[i][j] = Math.min(dp[i - 1][k] + moveCost[grid[i - 1][k]][j] + grid[i][j],
						 dp[i][j]);
				}
			}
		}
		n--;//为了方便枚举终点的路径最小值
		for (int j = 0; j < m; j++) {
          
   
			ans = Math.min(ans, dp[n][j]);//寻找达到尾部的最小值
		}
		return ans;

	}
}