考察:树形dp
思路:
设f[i][j]表示和为i,j==1表示经过了>=d的边,j=0表示未经过的方案数.以最后一步来划分集合,最后一步的和为i-j,此时边为j,那么状态转移方程是:
if(j>=d) f[i][1] = f[i-j][0]+f[i-j][1]
else f[i][1] = f[i-j][1] ,f[i][0] = f[i-j][0]
初始化f[0][0] = 1,也就是根节点的方案数为1.
注意:最后算出答案也不要忘了取模！！！
这道题用记忆化搜索没做出来,我果然菜
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int N = 110,Mod = 1000000007; 8 int n,k,d; 9 int f[N][2]; 10 int main() 11 { 12 scanf("%d%d%d",&n,&k,&d); 13 f[0][0] = 1; 14 for(int i=1;i<=n;i++) 15 for(int j=1;j<=k;j++) 16 { 17 if(j>i) continue; 18 if(j>=d) f[i][1] = (f[i-j][0]+f[i-j][1])%Mod+f[i][1]%Mod; 19 else f[i][1] = (f[i-j][1]+f[i][1])%Mod,f[i][0] = (f[i][0]+f[i-j][0])%Mod; 20 f[i][1]%=Mod; 21 f[i][0]%=Mod; 22 } 23 printf("%d\n",f[n][1]); 24 return 0; 25 }
原文：https://www.cnblogs.com/newblg/p/14411818.html