为什么这个动态编程代码不正确？

Question

我在做this家庭作业的问题。我使用标准的自下而上的动态规划算法解决了这个问题。我的代码显示了我的测试用例的预期结果，但该网站表示它给出了不正确的答案。我无法理解这段代码缺乏的地方。请帮帮我。

import java.io.*; 
import java.util.*; 
class Main300{ 

public static void main (String[] args) throws java.lang.Exception{ 
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    int nn = Integer.parseInt(br.readLine()); 
    for(int j = 0 ; j < nn; j++){ 
     int n = Integer.parseInt(br.readLine()); 
     char[][] a = new char[n][n]; 
     int ki = -1; 
     int kj = -1; 
     for(int i = 0 ; i < n ; i++){ 
      String s = br.readLine(); 
      for(int k = 0 ; k < n; k++){ 
       a[i][k] = s.charAt(k); 
       if(a[i][k] == 'K'){ 
        ki = i; 
        kj = k; 
       } 
      } 
     } 
     System.out.println(ans(a, ki, kj)); 
    } 
} 

private static int ans(char[][] a, int ki, int kj){ 
    int[][] x = new int[a.length][a.length]; 
    for(int j = a.length-1; j >= 0; j--){ 
     for(int i = 0 ; i < a.length; i++){ 
      if(a[i][j] == 'P'){ 
       x[i][j]++; 
      } 
      if(i-2 >= 0 && j+1 <= a.length-1 && a[i-2][j+1] == 'P'){ 
       x[i][j] += x[i-2][j+1]; 
      }else if(i-1 >= 0 && j+2 <= a.length-1 && a[i-1][j+2] == 'P'){ 
       x[i][j] += x[i-1][j+2]; 
      }else if(i+2 <= a.length-1 && j+1 <= a.length-1 && a[i+2][j+1] == 'P'){ 
       x[i][j] += x[i+2][j+1]; 
      }else if(i+1 <= a.length-1 && j+2 <= a.length-1 && a[i+1][j+2] == 'P'){ 
       x[i][j] += x[i+1][j+2]; 
      } 
     } 
    } 
    return x[ki][kj]; 
} 
} 

Answer 1

以下是错误答案的原因：

一）由于DP配方将

a[r][c] = max(a[r-2][c+1], a[r-1][c+2], a[r+1][c+2], a[r+2][c+1])

所以你需要从当前位置验证每一个路径。你的代码所暗示的是，你只能在一条路径上进行操作（else if's只模拟一条路径）。

b）同样@Vinayak指出，'a [i-2] [j + 1] =='P'可以让你移动到只有那些有一个棋子的地方，这不一定是真的。你可以考虑非常微不足道的例子来验证这一点。

下面是代码：

import java.io.*; 
import java.util.*; 

class e1_test{ 

    public static void main (String[] args) throws java.lang.Exception{ 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     int nn = Integer.parseInt(br.readLine()); 
     for(int j = 0 ; j < nn; j++){ 
      int n = Integer.parseInt(br.readLine());char[][] a = new char[n][n]; 
      int ki = -1; 
      int kj = -1; 
      for(int i = 0 ; i < n ; i++){ 
       String s = br.readLine(); 
       for(int k = 0 ; k < n; k++){ 
        a[i][k] = s.charAt(k); 
        if(a[i][k] == 'K'){ 
         ki = i; 
         kj = k; 
        } 
       } 
      } 
      System.out.println(ans(a, ki, kj)); 
     } 
    } 

    private static int ans(char[][] a, int ki, int kj) { 
     int[][] x = new int[a.length][a.length]; 
     for(int j = a.length-1; j >= 0; j--) { 
      for(int i = 0 ; i < a.length; i++) { 
       if(a[i][j] == 'P') { 
        x[i][j]++; 
       } 
       int temp=0; 
       //note the changes from else if's to only if's 
       //removal of [i-2][j+1] == 'P' condition. 
       if(i-2 >= 0 && j+1 <= a.length-1) { 
        if(temp < x[i-2][j+1]) 
         temp = x[i-2][j+1]; 
       } 
       if(i-1 >= 0 && j+2 <= a.length-1) { 
        if(temp < x[i-1][j+2]) 
         temp = x[i-1][j+2]; 
       } 
       if(i+2 <= a.length-1 && j+1 <= a.length-1) { 
        if(temp < x[i+2][j+1]) 
         temp = x[i+2][j+1]; 
       } 
       if(i+1 <= a.length-1 && j+2 <= a.length-1) { 
        if(temp < x[i+1][j+2]) 
         temp = x[i+1][j+2]; 
       } 
       x[i][j] += temp; 
      } 
     } 
     return x[ki][kj]; 
    } 
} 

Answer 2

我会稍微修改一下你的方法。你会发现这对DP解决方案非常有用。这将帮助你写出一个更简单的解决方案，并且你将自己解决你的WA问题。

取代检查边界，根据你的关系，使表TAB（x在你的代码中）稍微大点。

的TAB[r][c]值等于棋子的最大数量可以从(r, c)

捕获开始在白骑士问题，看看骑士怎么能去两行的上方和下方，2列到右边。所以请让你的TAB[N+4][N+2]而不是TAB[N][N]。在这种情况下，填充此基准值的额外空间0。

的关系是非常简单的

TAB[r][c] = max(TAB[r-2][c+1], TAB[r-1][c+2], TAB[r+1][c+2], TAB[r+2][c+1]) 

当然增量和（您已使用4 if-else编码）TAB[r][c]如果INP[r][c] == 'P'（a你的情况）

最后决赛解决方案是TAB[ki+2][kj]（ki, kj来自您的代码）。