如何应用递归

Question

问题陈述 :

您位于位置(x1,x2,...,xN)的N维网格中.网格的尺寸为(D1,D2,...... DN).在一个步骤中,您可以在N个维度中的任何一个中前进或后退一步.(因此总有2×N可能的不同动作).你有多少种方法可以采取M步,这样你就不会在任何时候离开网格？如果在任何点xi,你离开网格,xi≤0或xi> Di.

输入格式

第一行包含测试用例的数量T.T测试用例如下.对于每个测试用例,第一行包含N和M,第二行包含x1,x2,...,xN,第3行包含D1,D2,...,DN.

输出格式

输出T线,一个对应于每个测试用例.由于答案可能非常大,因此输出模数为1000000007.

约束

1≤T≤10

1≤N≤10

1≤M≤300

1≤Di≤100

1≤xi≤Di

样本输入

1

2 3

1 1

2 3

样本输出

12

如果这是1D,解决方案可以是这样的:solve(i + 1)+ solve(i-1);

在2D中:求解(i + 1,j)+求解(i-1,j)+求解(i,j + 1)+求解(i,j-1); 我如何为N Dimensions编程？它们是如上所述制作递归语句的一些常规步骤,可以帮助制作递归语句

我看到的大多数解决方案都是自下而上或自上而下的方式,我无法理解它们？是他们理解他们的任何方式,因为我总是使用递归+ memoization练习dp我觉得很难理解它们

如何做记忆？要使用哪种数据结构？,在哪里使用modulo 1e 7(仅在最终答案中)？

更新 感谢BARNEY解决方案,但在大多数情况下获得TLE如何更快地执行代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Grid_Walking {
    private static String[] n;
    private static int moves;

    private static HashMap<String, Integer> hm;
    private static BufferedReader br;

    private static String[] s;

    private static int dimen;
    private static int[] present;
    private static int[] dimlen;

    public static void main(String args[]) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t > 0) {
            n = br.readLine().split(" ");
            dimen = Integer.parseInt(n[0]);
            present = new int[dimen];
            dimlen = new int[dimen];
            moves = Integer.parseInt(n[1]);

            s = br.readLine().split(" ");
            for (int i = 0; i < dimen; i++) {
                present[i] = Integer.parseInt(s[i]) - 1;
            }
            s = br.readLine().split(" ");
            for (int i = 0; i < dimen; i++) {
                dimlen[i] = Integer.parseInt(s[i]);
            }
            hm = new HashMap<String, Integer>();
            System.out.println(solve(present, moves) % 1000000007);
            t--;
        }

    }

    private static int solve(int[] x, int moves) {
        // TODO Auto-generated method stub
        int result = 0;
        String s = Arrays.toString(x) + moves;
        if (hm.containsKey(s)) {
            return hm.get(s);
        }
        if (moves == 0) {
            return 1;
        }
        for (int i = 0; i < dimen; i++) {
            // System.out.println("fjfvnfjbv");
            if (x[i] > 0) {
                x[i] = x[i] - 1;
                result = result + solve(x, moves - 1);
                x[i] = x[i] + 1;
            }
            if (x[i] < dimlen[i] - 1) {
                x[i] = x[i] + 1;
                result = result + solve(x, moves - 1);
                x[i] = x[i] - 1;
            }
        }
        hm.put(s, result % 1000000007);
        return result % 1000000007;
    }
}

Answer 1

使用两级DP方法可以通过以下方式有效地解决此问题:

首先,分别解决每个维度的问题.这意味着对于每个维度,计算仅在该维度中生成0,1,...,M步骤的方式的数量(从给定的起始位置开始).您可以解决此问题,类似于您在建议的DP Java代码中描述它的方式.您可以将解决方案存储在整数矩阵中,其中行数对应于维数,列数为M + 1.请注意,对于每个维度,您不仅要计算制作M步骤的方式,还要计算制作M-1,M-2,...和0步骤的方式.我们需要第二级的这些信息.

其次,计算仅使用第一个j维度制作0,1,...,M步的方法的数量.假设您已经计算了仅使用第一个j-1维度制作0,1,...,M步的方法数.使用第一个j维度可以使用多少种方法来完成步骤？

• 您可以在维度j中创建0个步骤,并且我可以在维度<j中执行步骤
• 尺寸为j的1步或尺寸<j的i-1步,
• ...
• 或维度j的i-1步和维度<j的1步,
• 或者我在尺寸j中进行步骤,在尺寸<j中进行0步骤.

假设您在维度j中执行ik步骤,在维度<j中执行k步骤.在尺寸j中制作ik步骤的方法的数量已经在第一级计算了 - 让我们将这个数量表示为a.在维度<j中进行k步的方法的数量是递归计算的 - 让我们将该数量表示为b.然后,通过a*b*(i选择k)给出尺寸j中的尺寸j和k步骤的ik步骤的方式的数量.通过缓存计算结果,DP可用于使递归更有效(在这种情况下,密钥由两部分组成:维度j和步骤数量i).

请注意,您必须以1000000007的模数执行计算.为了计算质数的二项式系数,您可能会发现此链接很有用.