java - 寻找递归解的迭代解

Question

对于以下问题，我实现了递归和递归动态解决方案，但是我对迭代解决方案感兴趣(不是递归)。谁能帮我解决这个问题吗？

问题:

一只猫正在跳上 n 级楼梯，并且可以在同一位置跳 1 级、2 级或 3 级。时间。实现一个方法来计算猫跳上楼梯的可能方式。

对于迭代解决方案，我知道我们本质上必须计算下面值为 0 的三叉树的叶子

动态和递归解决方案:

import java.util.ArrayList;

public class Question1 {

    public static int countAndDisply(int n, ArrayList<Integer> hop) {
        if (n<0){
            return 0;
        }else{
            if (n==0) {
                for(int i:hop){
                    System.out.print(i+",");
                }
                System.out.println();
                return 1;
            }else{
                ArrayList<Integer> hop1 = new ArrayList<>(hop);
                hop1.add(1);
                ArrayList<Integer> hop2 = new ArrayList<>(hop);
                hop2.add(2);
                ArrayList<Integer> hop3 = new ArrayList<>(hop);
                hop3.add(3);
                return countAndDisply(n-1, hop1)+countAndDisply(n-2, hop2)+countAndDisply(n-3, hop3);

            }
        }

    }
    /**
     * Faster by using dynamic programming techniques to improve speed
     * We dont want to calculate the count(n) multiple times!
     * @param n
     * @param path
     * @return
     */
    public static int countFast(int n, int[] map){

        if (n<0){
            return 0;
        }else{
            if (n==0) {
                return 1;
            }else{
                if (map[n]>0){
                    return map[n];
                }else {
                    return countFast(n-1, map) + countFast(n-2, map) + countFast(n-3, map);
                }

            }
        }


    }

    public static int count(int n){

        if (n<0){
            return 0;
        }else{
            if (n==0) {
                return 1;
            }else{

                return count(n-1) + count(n-2) + count(n-3);


            }
        }


    }

    public static void main(String[] args) {
        int n=10;
        int [] map = new int[n+1];
        long startTime = System.nanoTime();
        System.out.println("Total number of possiblilities:"+Question1.countFast(n,map));
        long totalTime = System.nanoTime()-startTime;
        System.out.println("Time needed for dynamic recursive approach was(ns):"+totalTime);
        //System.out.println("Total number of possiblilities:"+Question1.AndDisply(n,new ArrayList<Integer>()));
        System.out.println("Total number of possiblilities:"+Question1.count(n));
         totalTime = System.nanoTime()-startTime;
        System.out.println("Time needed for pure recursive was(ns):"+totalTime);


    }

}

这里是输出:

Total number of possiblilities:274
Time needed for dynamic recursive approach was(ns):249311
Total number of possiblilities:274
Time needed for pure recursive was(ns):351088

Answer 1

如果你想迭代，最好的方法是从 0 开始，而不是从 n 开始。

一个例子:

i      i-1  i-2 i-3 sum

0   || -1   -2  -3  | 0   # does not contain any solution
1   || 0    -1  -2  | 1   # contains one solution (0)
2   || 1     0  -1  | 2   # contains two solutions (0,1) - (-1,-2)
3   || 2     1  0   | 4   # contains three solutions(0,1,2) 
                          #  2 (2) ,1(1) +1 (0) => 2+1+1 = 4
4   || 3     2  1   | 7   #  3 (4) ,2(2) 1 (1) => 4+2+1 = 7
5   || 4     3  2   | 13  # and so on
6   || 5     4  3   | 24
7   || 6     5  4   | 44
8   || 7     6  5   | 81
9   || 8     7  6   | 149
10  || 9     8  7   | 274

代码非常简单:

public static int solve(int n) {

        int[] map=new int[n+1];
        map[0]=1;
        map[1]=1;
        map[2]=2;
        for (int i = 3; i < map.length; i++) {
                map[i]+=map[i-1];
                map[i]+=map[i-2];
                map[i]+=map[i-3];
        }
        return map[n];
    }

当然，速度要快得多。