UVa-10943 How do you add

dp[i][j]表示把i拆成j个数的方法数

状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1] 可以想象成把这j个数字排成一列，dp[i-1][j]表示在第j个数的位置加1并更新状态继续考虑第j个数位置的情况（继续加1或者不加），dp[i][j-1]表示不再往第j个数的位置加数字，从而考虑第j-1个数位置的情况（加1或者不加）

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int mod=1e6; int dp[101][101]; int main(){ int N,K; while(cin>>N>>K&&(N+K)){ for(int i=1;i<=100;i++){ dp[1][i]=i; dp[i][1]=1; } for(int i=2;i<=100;i++){ for(int j=2;j<=100;j++){ dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;//至于mod为什么加在这里我也不懂 } } cout<<dp[N][K]<<endl; } return 0; }