題目以及輸入輸出描述：
題目很短，意思也很容易讀懂，
題目要求就是 有一只老鼠，進入了一個迷宮，迷宮地圖的大小為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提交里第一的- -
好了好了講解結束，本人只是個渣渣普通二本還在讀大二呢，這還是才第二篇博客- -如果有什么寫錯了，麻煩各位大佬高抬貴手不喜勿噴~.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137174.html
標籤：其他
下一篇：圖論篇5——關鍵路徑