第一次发帖时我想试试这个社区。

我已经研究了几个小时，但我似乎找不到足够接近的例子来从中获取灵感。我不在乎答案是什么语言，但更喜欢 java、c/c++ 或伪代码。

我希望在网格中找到长度为 n 的连续路径。

我找到了一个递归解决方案，我认为它很干净并且始终有效，但如果路径数量太多，运行时会很差。我意识到我可以迭代地实现它，但我想先找到一个递归解决方案。

我不在乎答案是什么语言，但我更喜欢 java、c/c++。

问题是—— 对于 String[] 和 int pathLength，该长度的路径有多少条。

{ "ABC", "CBZ", "CZC", "BZZ", "ZAA"} 长度为 3

This is the 3rd and 7th path from below.

A B C    A . C    A B .    A . .    A . .    A . .    . . .
. . .    . B .    C . .    C B .    . B .    . B .    . . .
. . .    . . .    . . .    . . .    C . .    . . C    C . .
. . .    . . .    . . .    . . .    . . .    . . .    B . .
. . .    . . .    . . .    . . .    . . .    . . .    . A .
(spaces are for clarity only) 

返回长度为 3 (A-B-C) 的 7 条可能路径

这是最初的递归解决方案

public class SimpleRecursive {

    private int ofLength;
    private int paths = 0;
    private String[] grid;

    public int count(String[] grid, int ofLength) {
        this.grid = grid;
        this.ofLength = ofLength;
        paths = 0;

        long startTime = System.currentTimeMillis();
        for (int j = 0; j < grid.length; j++) {
            for (int index = grid[j].indexOf('A'); index >= 0; index = grid[j].indexOf('A', index + 1)) {

                recursiveFind(1, index, j);

            }

        }
        System.out.println(System.currentTimeMillis() - startTime);
        return paths;
    }

    private void recursiveFind(int layer, int x, int y) {

        if (paths >= 1_000_000_000) {

        }

        else if (layer == ofLength) {

            paths++;

        }

        else {

            int xBound = grid[0].length();
            int yBound = grid.length;

            for (int dx = -1; dx <= 1; ++dx) {
                for (int dy = -1; dy <= 1; ++dy) {
                    if (dx != 0 || dy != 0) {
                        if ((x + dx < xBound && y + dy < yBound) && (x + dx >= 0 && y + dy >= 0)) {
                            if (grid[y].charAt(x) + 1 == grid[y + dy].charAt(x + dx)) {

                                recursiveFind(layer + 1, x + dx, y + dy);

                            }

                        }

                    }
                }
            }

        }
    }
}

这非常慢，因为每个新字母都可以衍生出 8 次递归，因此复杂性飙升。

我决定使用内存来提高性能。

这是我想出来的。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class AlphabetCount {

    private int ofLength;
    private int paths = 0;
    private String[] grid;
//  This was an optimization that helped a little.  It would store possible next paths  
//  private HashMap<Integer, ArrayList<int[]>> memoStack = new HashMap<Integer, ArrayList<int[]>>();
    //hashmap of indices that are part of a complete path(memoization saves)
    private HashMap<Integer, int[]> completedPath = new HashMap<Integer, int[]>();
    //entry point 
    public int count(String[] grid, int ofLength) {
        this.grid = grid;
        //Since i find the starting point ('A') by brute force then i just need the next n-1 letters
        this.ofLength = ofLength - 1;
        //variable to hold number of completed runs
        paths = 0;

        //holds the path that was taken to get to current place.  determined that i dont really need to memoize 'Z' hence ofLength -1 again
        List<int[]> fullPath = new ArrayList<int[]>(ofLength - 1);

        //just a timer to compare optimizations
        long startTime = System.currentTimeMillis();

        //this just loops around finding the next 'A'
        for (int j = 0; j < grid.length; j++) {
            for (int index = grid[j].indexOf('A'); index >= 0; index = grid[j].indexOf('A', index + 1)) {

                //into recursive function.  fullPath needs to be kept in this call so that it maintains state relevant to call stack?  also the 0 here is technically 'B' because we already found 'A'
                recursiveFind(fullPath, 0, index, j);

            }

        }
        System.out.println(System.currentTimeMillis() - startTime);
        return paths;
    }

    private void recursiveFind(List<int[]> fullPath, int layer, int x, int y) {
        //hashing key. mimics strings tohash.  should not have any duplicates to my knowledge
        int key = 31 * (x) + 62 * (y) + 93 * layer;

        //if there is more than 1000000000 paths then just stop counting and tell me its over 1000000000
        if (paths >= 1_000_000_000) {

        //this if statement never returns true unfortunately.. this is the optimization that would actually help me.
        } else if (completedPath.containsKey(key)) {
            paths++;
            for (int i = 0; i < fullPath.size() - 1; i++) {
                int mkey = 31 * fullPath.get(i)[0] + 62 * fullPath.get(i)[1] + 93 * (i);
                if (!completedPath.containsKey(mkey)) {
                    completedPath.put(mkey, fullPath.get(i));
                }
            }

        }
        //if we have a full run then save the path we took into the memoization hashmap and then increase paths 
        else if (layer == ofLength) {

            for (int i = 0; i < fullPath.size() - 1; i++) {
                int mkey = 31 * fullPath.get(i)[0] + 62 * fullPath.get(i)[1] + 93 * (i);
                if (!completedPath.containsKey(mkey)) {
                    completedPath.put(mkey, fullPath.get(i));
                }
            }

            paths++;

        }


//everything with memoStack is an optimization that i used that increased performance marginally.
//      else if (memoStack.containsKey(key)) {
//          for (int[] path : memoStack.get(key)) {
//              recursiveFind(fullPath,layer + 1, path[0], path[1]);
//          }
//      } 

        else {

            int xBound = grid[0].length();
            int yBound = grid.length;

            // ArrayList<int[]> newPaths = new ArrayList<int[]>();
            int[] pair = new int[2];

            //this loop checks indices adjacent in all 8 directions ignoring index you are in then checks to see if you are out of bounds then checks to see if one of those directions has the next character
            for (int dx = -1; dx <= 1; ++dx) {
                for (int dy = -1; dy <= 1; ++dy) {
                    if (dx != 0 || dy != 0) {
                        if ((x + dx < xBound && y + dy < yBound) && (x + dx >= 0 && y + dy >= 0)) {
                            if (grid[y].charAt(x) + 1 == grid[y + dy].charAt(x + dx)) {

                                pair[0] = x + dx;
                                pair[1] = y + dy;
                                // newPaths.add(pair.clone());
                                //not sure about this... i wanted to save space by not allocating everything but i needed fullPath to only have the path up to the current call
                                fullPath.subList(layer, fullPath.size()).clear();
                                //i reuse the int[] pair so it needs to be cloned
                                fullPath.add(pair.clone());
                                //recursive call
                                recursiveFind(fullPath, layer + 1, x + dx, y + dy);

                            }

                        }

                    }
                }
            }
            // memoStack.putIfAbsent(key, newPaths);

            // memo thought! if layer, x and y are the same as a successful runs then you can use a
            // previous run

        }
    }

}

问题是我的内存从未真正被使用过。递归调用有点模仿深度优先搜索。 ex-

     1
   / | \
  2  5  8
 /\  |\  |\
3 4  6 7 9 10

因此保存一个运行不会以任何性能节省方式与另一个运行重叠，因为它在返回调用堆栈之前在树的底部进行搜索。所以问题是......我如何记住这个？或者一旦我完全运行，我如何递归回到树的开头，以便我编写的内存有效。

真正扼杀性能的测试字符串是 { "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "ABCDEFGHIJKLMNOPQRSTUVWXYZ"}; 对于所有长度为 26 的路径 (应返回 1000000000)

附言。作为第一次发布者，任何关于一般代码改进或不良编码习惯的评论都将不胜感激。另外，因为我之前没有发帖，如果这个问题不清楚或者格式不正确或太长等，请告诉我。

最佳答案

我不确定你在内存什么(也许你可以用文字解释一下？)但这里似乎有重叠的子问题。如果我理解正确，除了“A”之外，字母的任何特定实例都只能从字母表中相邻的前一个字母到达。这意味着我们可以存储来自字母的每个特定实例的路径数。当在后续场合到达该特定实例时，我们可以避免递归到它。

深度优先搜索:

 d1 d2 d3 d4
   c1   c2
      b
    a1 a2

 .....f(c1) = f(d1) + f(d2) = 2
 .....f(c2) = f(d3) + f(d4) = 2
 ...f(b) = f(c1) + f(c2) = 4
 f(a1) = f(b) = 4
 f(a2) = f(b) = 4

关于java - 如何内存长度为 n 的递归路径搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55250279/