牛牛回家要走n个台阶，每次最多跨m个台阶，最少跨一个台阶。要求每次和之前两步走的台阶数目不能相同。求有多少种不同的走法，答案对1e9+7取模。
输入n,m，表示台阶数目和单步跨越的最多台阶数目。1<= n <= 100000, 2<=7。
输出答案。
输入
7 3
输出
2
说明合法的走法仅有(1,2,3,1),(1,3,2,1)。比如(1,2,1,3)在第三步非法。
#include<bits/stdc++.h> typedef long long int ll; using namespace std; int MOD=1000000007; int v[8][8][100005]={0}; void help(int& res,int a,int b,int n,int m){ if(n==0) res=(res+1)%MOD; else if(n<0) return; else{ for(int i=1;i<=m;i++){ if(i!=a&&i!=b){ if(v[b][i][n-i]==0) { int mm=0; help(mm,b,i,n-i,m); v[b][i][n-i]=mm; res=(res+mm)%MOD; } else{ res=(res+v[b][i][n-i])%MOD; } } } } } int main(){ int n,m; cin>>n>>m; int res=0; help(res,0,0,n,m); cout<<res<<endl; return 0; } ll steps[100001][8][8] = {0}; //第二种方法 static ll backtracking(int n, int m, int pre1, int pre2){ if(n <= 0) return n == 0 ? 1 : 0; if(steps[n][pre1][pre2] != 0){ return steps[n][pre1][pre2]; } ll cnt = 0; for(int i = 1;i <= m; ++i){ if(i != pre1 && i != pre2){ cnt += backtracking(n - i, m, i, pre1); } } steps[n][pre1][pre2] = cnt % MOD; return steps[n][pre1][pre2]; }
