Pitanje ili opis problema
Cao, ja imam jedno resenje dp problema za koje mislim da je okej, medjutim padaju mi dva test primera. Zadtak jos nije resio pa je mozda do test primera. Naime, nije receno sta da se ispise ako ne postoji resenje. Ovo je moj kod:
#include<bits/stdc++.h>
using namespace std;
int n,s;
int a[1050];
int dp[1050][1050];
int main(){
cin>>s>>n;
for(int i=0; i<n; i++)
cin>>a[i];
for(int i=0; i<n; i++)
for(int j=1; j<=s; j++)
dp[i][j]=-1;
for(int i=0; i<=s; i++)
if(i%a[0]==0)
dp[0][i]= i/a[0];
for(int i=1; i<n; i++){
int j=1;
while(a[i]>j){
dp[i][j]= dp[i-1][j];
j++;
}
for(; j<=s; j++){
if((dp[i-1][j]==-1) && (dp[i][j-a[i]]==-1))
dp[i][j]=-1;
else if(dp[i-1][j]==-1){
dp[i][j]=dp[i][j-a[i]]+1;
}
else if(dp[i][j-a[i]]==-1){
dp[i][j]=dp[i-1][j];
}
else
dp[i][j]= min(dp[i][j-a[i]]+1, dp[i-1][j]);
}
}
cout<<dp[n-1][s]<<"\n";
return 0;
}
Link ka zadatku ili odgovarajućoj stranici
https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/isplata_sa_najmanje_novcica#solution