首页 > 试题广场 >

精灵鼠从入口到出口的最少减少速度

[编程题]精灵鼠从入口到出口的最少减少速度

热度指数：3269 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？

输入描述:

第一行迷宫的大小: n >=2 & n <= 10000；
第2到n+1行，每行输入为以','分割的该位置的减速,减速f >=1 & f < 10。

输出描述:

精灵鼠从入口到出口的最少减少速度？

示例1

输入

3
5,5,7
6,7,8
2,2,4

输出

算法知识视频讲解

白伟仝

发表于 2020-04-29 18:05:12

import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = Integ 展开全文

一曲离殇、

发表于 2019-12-02 13:52:36

bandiaoz

发表于 2024-12-25 23:47:05

解题思路这是一道典型的动态规划题目，主要思路如下：由于精灵鼠只能向右或向下移动，所以可以使用动态规划求解状态定义：dp[i][j] 表示从起点到达位置的最小减速总和状态转移方程：第一行：dp[0][j] = dp[0][j-1] + num[0][j] 第一列：dp[i][0] 展开全文

laglangyue

发表于 2020-06-07 20:52:49

二维dp,复杂度o(n^2)，和斐波那契数列一样，当前源自两步，要么来自上，要么来自左。流式编程处理输出输出。 import java.util.Arrays; import java.util.Scanner; public class Main { public static void 展开全文