需要动态规划解决方案

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）。解决问题就足够了。