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} \]

这篇关于数据结构与算法-最小路径和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!