需要動態規劃解決方案

Question

problem是以下內容：

給定一個字符矩陣。在遊戲的最初階段，我處於矩陣中的位置（0,0）。根據當前位置（i，j）中的字符，我可以向上移動（如果當前字符是'U'），如果當前字符是'D'則向下移動，如果當前字符是'R'當前字符是'L'。一旦我到達具有'*'字符的位置，我就不能再移動了（正好有一個這樣的位置）。我有一段時間K我必須達到這個角色。我也有權改變角色，s.t.我可以更快地達到'*'字符，但是每改變一次，我都要花費1美元。最後，我必須返回我執行s.t.的最小數量的更改。我必須在時間k達到'*'字符。如果不可能，我必須返回-1。

我的想法是：

1. 遍歷整個矩陣，找到字符的位置「*」。

2. 創建布爾方法isReachable(x, y, k)，它告訴我，如果在字符位置(x, y)從(0, 0)位置到達時間k。下面是該方法：

   public static boolean isReachable(int x, int y, int time){ 
       if(time < 0){ 
        return false; 
       } 
       if(x == 0 && y == 0){ 
        return true; 
       } 
       if(isInBounds(x-1, y)){ 
        if(maze[x-1][y] == 'D'){ 
         return isReachable(x-1, y, time-1); 
        } 
       } 
       if(isInBounds(x, y-1)){ 
        if(maze[x][y-1] == 'R'){ 
         return isReachable(x, y-1, time-1); 
        } 
       } 
       if(isInBounds(x+1, y)){ 
        if(maze[x+1][y] == 'U'){ 
         return isReachable(x+1, y, time-1); 
        } 
       } 
       if(isInBounds(x, y+1)){ 
        if(maze[x][y+1] == 'L'){ 
         return isReachable(x, y+1, time-1); 
        } 
       } 
       return false; 
       } 
   
       private static boolean isInBounds(int x, int y) { 
       if(x >= 0 && x <= N-1 && y >= 0 && y <= M-1){ 
        return true; 
       } 
       return false; 
   } 
   

如果該方法返回真 - I輸出0（即沒有必要改變在基體的任何正方形）。

如果該方法返回false - 我想要執行另一個方法，它會告訴我最少的變化。但是我不知道如何寫它。這是我的草案obiously不工作：

private static int find(int x, int y, int k) { 
    int res = 0; 
    if(k < 0){ //my idea is that if the time become < 0 it means that the point is unreachable, i.e. I have to output 0; Howevr this doesnt output 0, just gives 0 to the upper levels of a recursion tree; 
     return -1; 
    } 
    if(x == 0 && y == 0){ 
     res = 0; 
    } 
    else{ 
     int down; 
     if(isInBounds(x-1, y)){ 
      if(maze[x-1][y] == 'D'){ 
       down = find(x-1, y, k-1); 
      } 
      else{ 
       down = 1 + find(x-1, y, k-1); 
      } 
     } 
     else{ 
      down = Integer.MAX_VALUE; 
     } 
     int left; 
     if(isInBounds(x, y+1)){ 
      if(maze[x][y+1] == 'L'){ 
       left = find(x, y+1, k-1); 
      } 
      else{ 
       left = 1 + find(x, y+1, k-1); 
      } 
     } 
     else{ 
      left = Integer.MAX_VALUE; 
     } 
     int right; 
     if(isInBounds(x, y-1)){ 
      if(maze[x][y-1] == 'R'){ 
       right = find(x, y-1, k-1); 
      } 
      else{ 
       right = 1 + find(x, y-1, k-1); 
      } 
     } 
     else{ 
      right = Integer.MAX_VALUE; 
     } 
     int up; 
     if(isInBounds(x+1, y)){ 
      if(maze[x+1][y] == 'U'){ 
       up = find(x+1, y, k-1); 
      } 
      else{ 
       up = 1 + find(x+1, y, k-1); 
      } 
     } 
     else{ 
      up = Integer.MAX_VALUE; 
     } 
     res = min(left, right, up, down); 
    } 
    return res; 
} 

正如我在我有兩個非常基本情況的意見，我不知道如何執行寫道：

• 到時候< 0 - >它意味着該點無法到達，即我必須輸出-1（但我不知道該怎麼做）
• 如果我在點（0，0）我不必做任何更改 - 返回0
• 否則，我會檢查鄰近的方塊是否有他們的字母，並返回我從他們那裏得到的。

有人可以幫助我的一般想法，因爲我認爲我是錯的。我說的問題描述，我們必須使用動態編程和遞歸

Answer 1

我還沒有解決問題，但我認爲我的解決方案是正確的。 create dp [i] [j] [dir] [step]意味着pos（i，j）中的代價，方向是dir，需要'step'步驟到位置'*'。我們需要計算dp [I] [J] [0 | 1 | 2 | 3] [0]。 tot time是state * move，即（50 * 50 * 4 * 1000）*（4 * 4）。解決問題就足夠了。