精灵鼠从入口到出口最少减少速度（2019年哔哩哔哩校招真题）题解
题目以及输入输出描述：
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
题目很短。意思也很容易读懂。
题目要求就是 有一只老鼠，进入了一个迷宫，迷宫地图的大小为n*n。老鼠要从（起点）（0，0）坐标位置 到达 终点 （n-1,n-1）的位置。
老鼠的行动方式只有两种 —— 向下和向前。
每一个点都会让老鼠的速度降低（减少）。求老鼠到达终点的时候最少减少的速度。
解题思路：
我们先考虑最后一步 到达终点，这一步可以从哪里来呢？根据题目分析因为老鼠只可以向下或者向前。所以到达终点（n-1，n-1）前，老鼠不是在（n-1，n-2），
就是在（n-2,n-1）; 这样我们可以得出，到达每一个点之前老鼠的位置只有两种可能——该点的上方或者该点的后方（左方）。其实这样子的思想就是动态规划的思想。
把问题从一个阶段分成多个单阶段。每到达一个点就是一个单阶段。根据每一个单阶段的的关系求解。每个单阶段（每到达一个点）的上一阶段（上一个点）只可能是该点上方
或者左方。这就是关系。 而题目求的是最少的减少速度。 正好我们的 每一阶段对应的上一阶段有两种。那么我们求解的时候就可以做选择。把该点的最少减少速度表示为：
当前点的减少速度 + 最小值（上一阶段（点）左方，上一阶段(点)上方减少速度）; 则就是利用了关系求解 也可以说是一条递推的式子。我们从（0，0）递推到尾（n-1，n-1）；
最终的便是答案。
解题代码：
1 import java.util.Scanner; 2
3 public class Main{ 4
5 public static void main(String[] args) { 6 Scanner in = new Scanner(System.in); 7 int n; 8 n = in.nextInt(); 9 int[][] dp = new int[n][n]; 10 char[][] loseSpeed = new char[n][n]; 11 for (int i = 0; i < n; i++) { 12 String str = in.next(); 13 int index = 0; 14 for (int j = 0; j < n; j++) { 15 loseSpeed[i][j] = str.charAt(index); 16 index += 2; 17 } 18 } 19 dp[0][0] = loseSpeed[0][0] - 48; 20 for(int i=1;i<n;i++){ 21 dp[i][0]=dp[i - 1][0] + (loseSpeed[i][0] - 48); 22 dp[0][i]=dp[0][i - 1] + (loseSpeed[0][i] - 48); 23 } 24 for (int i = 1; i < n; i++) 25 for (int j = 1; j < n; j++) { 26 dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + (loseSpeed[i][j] - 48); 27 } 28 System.out.println(dp[n - 1][n - 1]); 29 } 30 }
这题的输入格式有点刁钻。中间会夹杂着 逗号。所以输入的处理有点讲究（个人觉得- -）。这里我采用的是用 loseSpeed这个char类型的二维数组来表示地图。lose[i][j]表示的就是（i,j）点减少的速度。
而dp这个int类型的二维数组数组 则就是递推求解过程中存储答案的。dp[i][j]表示(到达i,j)点最少的减少速度。
递推前先把边界处理好。(0,0)点是起点 所以 dp[0][0]就是loseSpeed[0][0] 的int 值。
而对与地图的最上方（第一行） 老鼠只可以从左方到达该点无法从上方下来。所以 对于第一行dp[0][j] 就是 dp[0][j] +dp[0][j-1];
同理 地图最左方（第一列），只可以从上方下来无法从左方向前到达，所以对于第一列dp[i][0] 就是dp[i-1][0] + dp[i][0];
而其余的点就是正常的递推就好。
吐槽一下:搞不懂这时间的咋回事- -。之前AC的时候是只需要300多ms的，而现在
要400多ms了- -，搞不懂为啥不稳定啦- -。300多ms 的时候还是Java提交里第一的- -
好了好了讲解结束，本人只是个渣渣普通二本还在读大二呢。这还是才第二篇博客- -如果有什么写错了，麻烦各位大佬高抬贵手不喜勿喷~.
