Java教程

数据结构与算法-最小路径和

本文主要是介绍数据结构与算法-最小路径和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目路径

最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例1：
image

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

题解

此题为动态规划，重点列出转移方程，此题边界条件较为简单。

\[dp[i][j] = \begin{cases} dp[0][j−1]+grid[0][j] & \text{ if } i=0, j>0\\ dp[i−1][0]+grid[i][0] & \text{ if } i>0, j=0 \\ dp[i−1][0]+grid[i][0] & \text{ if } i>0, j>0 \end{cases} \]

这篇关于数据结构与算法-最小路径和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航