#include<stdio.h>
#include
#include
#include
#include
#include<unordered_map>
using namespace std;
int main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
int di[n],fu[n];
int dp[1001];
for(int i=1;i<=1001;i++) dp[i]=0;
int ma = -1,ch=1e9;
for(int i=0;i<n;i++) {
cin>>di[i];
if(ma<di[i]) ma = di[i];
if(ch>di[i]) ch = di[i];
}
for(int i=0;i<n;i++){
cin>>fu[i];
if(dp[fu[i]]==0) dp[fu[i]] = 1;
}
for(int i=ch;i<=2*ma;i++){
int mini = 1e9;
// cout<<dp[i]<<" ";
if(dp[i]==0){
for(int j=n-1;j>=0;j--){
// cout<<i<<" - "<<j<<endl;
if(i>=fu[j]){
if(mini>(1+dp[i-fu[j]]) && dp[i-fu[j]]!=0){
mini = 1+dp[i-fu[j]];
dp[i] = mini;
}
}
}
}
}
//for(int i=1;i<=2*ma;i++) cout<<dp[i]<<" ";
int sum = 0;
for(int i=0;i<n;i++){
sum = sum + dp[di[i]*2];
}
cout<<sum<<endl;
}
return 0;
}
Has someone come across the reduce to one dynamic problem ? I used that strategy in the Pizza Delivery Boy (DBOY) problem , can someone point out what is going wrong here ?