题解思路

问题转换

给定一个 M×N 的费用网格，从左上角走到右下角，每次只能向右或向下走，经过每个格子的费用累加，求最小总费用。

动态规划

1. 定义状态
   令 dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 的最小费用。
2. 状态转移
   • 边界条件：

题目内容

小红计划来个自驾游到某一著名景点，网上找了有多条路可以过去，不同的路段收费不一样，小红特地收集了路上的收费信息。

请帮小红规划一条最经济的路径，并输出所需的过路费。

说明：

(1)小红从左上角的顶点出发，目的地为右下角；

(2)假设小红经过的路径为 $1>1>4>2>1$ ，那么小红所支付的过路费为 $1+1+4+2+1=9$

输入描述

先输入 $M$

再依次输入 $M$ 个 $1*N$ 数组，数据中数字以空格分开

输出描述

数字，即所需支付的最少过路费

样例1

输入

3
1 3 1
1 5 1
4 2 1

输出

7