This is my code . All test cases are passing except 1 test case . Can you tell me , where did go wrong in my logic ?
import java.util.*;
public class Main {
public static void main(String args[]) {
// Your Code Here
Scanner scan = new Scanner(System.in) ;
int n = scan.nextInt() ;
int w = scan.nextInt() ;
int[] wt = new int[w] ;
for(int i = 0 ; i < w ; i ++){
wt[i] = i + 1 ; // weight array
}
int[] prices = new int[w] ;
for(int i = 0 ; i < w ; i ++){
prices[i] = scan.nextInt() ;
}
//int[][] strg = new int[w][w+1] ;
//System.out.println(minMoney(wt,prices,0,w)) ;
//System.out.println(minMoneyTD(wt,prices,0,w,strg)) ;
System.out.println(minMoneyBU(wt,prices,w)) ;
}
// Recursive code
public static int minMoney(int[] wt , int[] prices ,int i , int w ){
if(w == 0){
return 0 ;
}
if(i == wt.length){
return -1 ;
}
int in = -1 ;
if(w >= wt[i] && prices[i] != -1){
in = minMoney(wt,prices,i+1,w-wt[i]) ;
if(in != -1){
in += prices[i] ;
}
}
int ex = minMoney(wt,prices,i+1,w) ;
if(in == -1){
return ex ;
}
if(ex == -1){
return in ;
}
int ans = Math.min(in,ex) ;
return ans ;
}
// Top Down DP code
public static int minMoneyTD(int[] wt , int[] prices ,int i , int w ,int[][] strg){
if(w == 0){
return 0 ;
}
if(i == wt.length){
return -1 ;
}
if(strg[i][w] != 0){
return strg[i][w] ;
}
int in = -1 ;
if(w >= wt[i] && prices[i] != -1){
in = minMoneyTD(wt,prices,i+1,w-wt[i],strg) ;
if(in != -1){
in += prices[i] ;
}
}
int ex = minMoneyTD(wt,prices,i+1,w,strg) ;
if(in == -1){
strg[i][w] = ex ;
return ex ;
}
if(ex == -1){
strg[i][w] = in ;
return in ;
}
int ans = Math.min(in,ex) ;
strg[i][w] = ans ;
return ans ;
}
// Bottom Up DP code
public static int minMoneyBU(int[] wt , int[] prices , int w){
int[][] strg = new int[w+1][w+1] ;
for(int row = w ; row >= 0 ; row --){
for(int col = w ; col >= 0 ; col --){
if(col == 0){
strg[row][col] = 0 ;
continue ;
}
if(row == w){
strg[row][col] = -1 ;
continue ;
}
int in = -1 ;
if(col >= wt[row] && prices[row] != -1){
in = strg[row+1][col-wt[row]] ;
if(in != -1){
in += prices[row] ;
}
}
int ex = strg[row+1][col] ;
if(in == -1){
strg[row][col] = ex ;
continue ;
}
if(ex == -1){
strg[row][col] = in ;
continue ;
}
int ans = Math.min(in,ex) ;
strg[row][col] = ans ;
}
}
return strg[0][w] ;
}
}