arrays - 打印 True 或 False

Question

给定一个整数数组，m=步数。从索引 0 开始。每次移动，您都可以向前或向后走 arr[i] 步。如果 m 变为 0。并且你在最后一个位置，则打印 true 否则打印 false。

例如:arr 包含元素 2、3、1。m=1;回答:是的；解释:i=0 处的值为 2，因此对于 m=1，向前走 2 步，您将到达终点位置。所以，真的。

我试过下面的代码，但它没有打印出正确的答案:num_ele 是数组中元素的总数。

bool fun(int arr[],int m,int i,int num_ele)
{
    if(m==0)
    {
        if(i==(num_ele)
            return true;
        else
            return false;
    }
    fun(arr,m-1,i+arr[i],num_ele);
    fun(arr,m-1,i-arr[i],num_ele);
}

Answer 1

这个问题等同于确定二进制字母表上的确定性有限自动机是否接受长度为 m 的字符串的问题。要构造自动机，请添加与数组元素一样多的状态，并添加两个转换以表示向左或向右移动相应数量的位置。使接受的最后一个数组元素对应的状态，使第一个数组元素对应的状态为初始状态。

接下来，构造一个确定性有限自动机，它接受长度正好为 n 的所有二进制字符串。这个 DFA 将有 n+1 个状态，一个初始状态和一个接受状态。

接下来，使用笛卡尔积机构造为这些 DFA 的语言的交集构造一个 DFA。该 DFA 将对上述两个 DFA 的每一对状态都有一个状态，将从与初始状态对对应的状态开始，并在与接受状态对对应的状态终止。

最后判断这个DFA的语言是否为空语言。广度优先或深度优先搜索，或最小化，然后与空语言的 DFA 进行比较，就足够了。

您从两个具有 n 和 n+1 个状态的 DFA 开始；构建具有 n(n+1) 个状态的 DFA；然后看看它是否接受字符串。复杂度应该是 O(n^2)。