回家有n个台阶，每次至少走一个，但是要求每步和之前两步走的台阶数目不能一样，请问有多少种不同的解法，答案对10^9+7取模。
输入两个整数n，m，n表示台阶数目，m表示单步最大跨越的台阶数目。
思路：老实说这题不难，但是想全A还是有点难，全A肯定要动态规划，而且是三维的动态规划，但是我觉得面试的时候也不会考这么难，所以三维的动态规划的方法就不写了，下面写了两个方法，一个是递归的，一个是记忆化搜索（带备忘录的递归）。
1、递归
就是递归每次需要传入上一次的值last和上上次的值lastlast，然后遍历可以跳跃的值1~m，如果不是last和lastlast就可以继续递归，否则跳过，代码如下：
public static int res=0; public static void dfs1(int index,int n,int m,int last,int lastlast){ if(index==n) { res++; res=res%1000000007; } if(index>n) return ; for(int i=1;i<=m;i++){ if(i!=lastlast&&i!=last){ dfs1(index+i,n,m,i,last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } }2、带备忘录的递归
大家都知道，递归的低效率是由于重复计算了很多子问题，因此想到把子问题保存在哈希表里面，每次递归时直接查询，如果哈希表里面没有才继续往下算，代码如下：
public static HashMap<String,Integer> map; public static int dfs(int index,int n,int m,int last,int lastlast){ if(index==n) { return 1; } if(index>n) return 0; String str=index+","+last+","+lastlast; if(map.containsKey(str)) return map.get(str); int lastres=0; for(int i=1;i<=m;i++){ if(i!=lastlast&&i!=last){ lastres+=dfs(index+i,n,m,i,last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } lastres=lastres%1000000007; map.put(str,lastres); return lastres; }最后把两个代码放在一起，方便大家比较：
public static int res=0; public static HashMap<String,Integer> map; public static int dfs(int index,int n,int m,int last,int lastlast){ if(index==n) { return 1; } if(index>n) return 0; String str=index+","+last+","+lastlast; if(map.containsKey(str)) return map.get(str); int lastres=0; for(int i=1;i<=m;i++){ if(i!=lastlast&&i!=last){ lastres+=dfs(index+i,n,m,i,last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } lastres=lastres%1000000007; map.put(str,lastres); return lastres; } public static void dfs1(int index,int n,int m,int last,int lastlast){ if(index==n) { res++; res=res%1000000007; } if(index>n) return ; for(int i=1;i<=m;i++){ if(i!=lastlast&&i!=last){ dfs1(index+i,n,m,i,last);//在里面进行修改，这一步的值在下一步就是last，last在下一步就是lastlast } } } public static void print(List<List<Integer>> tmp){ for(List<Integer> a:tmp){ for(Integer a1:a) System.out.print(a1+" "); System.out.println(); } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); //int n=70; //int m=4; int n=sc.nextInt(); int m=sc.nextInt(); map=new HashMap<>(); System.out.println("带备忘录的："); System.out.println(dfs(0,n,m,0,0)); dfs1(0,n,m,0,0); System.out.println("不带备忘录的"); System.out.println(res); }
