动态规划习题，关系式推导和求模技巧

#include <stdio.h>
int dp[100001]= {0};
int main()
{
int n,i;
scanf("%d",&n);
int mod=100003;
dp[0]=dp[1]=dp[2]=dp[3]=1;
//dp[i]=dp[i-1]+dp[i-4]+dp[i-7]…
//dp[i-3]=dp[i-4]+dp[i-7]+dp[i-9]…i-3后面有的项和dp[i]是一样的
//dp[i]=dp[i-1]+dp[i-3]
for(i=4; i<=n; ++i)
dp[i]=(dp[i-1]+dp[i-3])%mod;//先加再mod和先mod再加结果一样 (a+b)%c=(a&c+b%c)%c 按照递归的思想，dp[i-1]和dp[i-3]之前都mod过了，他们求和再mod，等价于整个数组都先求和再mod

printf("%d",dp[n]);
return 0;
}