求优化 dp

#include<bits/stdc++.h>
using namespace std;
#define int long long
int tr[15]={1,3,6,10,15};
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int dp(int n){
    vector<int>dp(n+1,numeric_limits<int>::max());
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<5;j++){
            if(i>=tr[j])dp[i]=min(dp[i],dp[i-tr[j]]+1);
        }
    }
    return dp[n];
}
signed main(){
	int t=read();
	while(t--){
		int n=read(); 
		cout<<dp(n)<<"\n";
	}
	return 0;
}

优化到 o(logn^2)左右？（实在优化不了了也可以看看可不可以写一个优异点的算法？）