dp[i][j] 記錄最大的數不超過i，和為j的方法數

dp[i][j]=dp[i-1][j]+dp[i][j-I*I*i]  前半部分表示不使用i，后半部分表示使用i

#include<iostream>#include<cstring>using namespace std;long long dp[23][10000+5];int main(){	int n;	memset(dp,0,sizeof(dp));	dp[0][0]=1;	while(cin>>n){		for(int i=1;i<=21;i++){			for(int j=0;j<=n;j++){				if(j>=i*i*i) dp[i][j]=dp[i-1][j]+dp[i][j-i*i*i];				else dp[i][j]=dp[i-1][j];			}		}		cout<<dp[21][n]<<endl;	}	return 0;}
利用滾動數組進行優化
#include<iostream>#include<cstring>using namespace std;long long dp[10000+5];int main(){	int n;	while(cin>>n){		memset(dp,0,sizeof(dp));		dp[0]=1; 		for(int i=1;i<=21;i++){			for(int j=0;j<=n;j++){				if(j>=i*i*i) dp[j]=dp[j]+dp[j-i*i*i];			}		}		cout<<dp[n]<<endl;	}	return 0;}