AOJ 0096 Sum of 4 Integers II

こんにちは川です。

今回はdpですね。やはり勉強しないといけない。

ソースコード

#include<bits/stdc++.h>

using namespace std;

int dp[4][4001]={};

int main()

{

    for(int i=0;i<1001;i++)dp[0][i]++;

    for(int i=1;i<4;i++){

        for(int j=4000;j>-1;j--){

            for(int k=0;k<1001;k++){

                if(j-k<0)break;

                dp[i][j]+=dp[i-1][j-k];

            }

        }

    }

    int n;

    while(cin>>n)cout<<dp[3][n]<<endl;

}