使用递归解决矩阵问题时得到错误答案

user1 发表于 Dev

用户1

问题是：给定具有随机 (0, 1) 值的 mXn 矩阵。从最开始的位置开始向 m-1, n-1 位置（最后一个位置）移动，我们可以移动的唯一方向是向下或向右。

规则：

如果找到 1 个无法移动
唯一可能的移动是 0 所以找到到达 (m-1, n-1) 位置的可能方法。

示例：matrix((0, 0, 0), (0, 0, 0), (0, 0, 0)) 答案：6

这是我的逻辑：

public class Main {
    static int possibility = 0;
    static int r = 3;
    static int c = 3;
    public static void main(String[] args) {
        int array[][] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
        // int array[][] = {{0, 1, 1}, {0, 0, 1}, {1, 0, 0}};
        matrixProblem(array, 0, 0);
        System.out.println("total possible solutions: ");
        System.out.println(possibility);
    }    

    static void matrixProblem(int[][] array, int i, int j) {
        if (i == r - 1 && j == c - 1) {
            possibility++;
            return;
        }

        if(i+1 < r) {
            if(array[++i][j] == 0) {
                matrixProblem(array, i, j);
            }
        }

        if(j+1 < c) {
            if(array[i][++j] == 0) {  
                matrixProblem(array, i, j);
            }
        }
    }
}

根据我的逻辑，它给出了错误的答案。

拉什卡迪瓦

您的逻辑几乎是正确的，但是问题出在递归调用时，您正在传递递增的i值，而不是仅传递i+1。j 值相同。

编辑1：

 if(i+1 < r) {
        if(array[i+1][j] == 0) {
                matrixProblem(array, i+1, j);
            }
        }

        if(j+1 < c) {
            if(array[i][j+1] == 0) {  
                matrixProblem(array, i, j+1);
            }
        }
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。