Dynamic Programming Doubt

#1

Do I always have to arrive at bottom up solution while solving dp problems? Top down approach will not suffice?

#2

I have used memoization here but it’s giving TLE . Memoization should not give TLE right?

#3

@ap8730390
bottom up Dp is faster than Top down

Top down approach will not suffice?
in some Cases may be Give Tle
your doing wrong here .
else {
int o1 = cost[i] + knapsack(wt, cost, cap - wt[i], i + 1); // above fun call kr rahe ho
int o2 = knapsack(wt, cost, cap, i + 1);

		ans = Math.max(o1, o2);
	}
#4

@ap8730390
Top down

// correct code

import java.util.*;

class Main {
public static Scanner scn = new Scanner(System.in);

public static void main(String[] args) {
	int n = scn.nextInt();
	int s = scn.nextInt();

	int[] wt = new int[n];
	int[] val = new int[n];

	for (int i = 0; i < n; i++) {
		wt[i] = scn.nextInt();
	}
	for (int i = 0; i < n; i++) {
		val[i] = scn.nextInt();
	}

	// System.out.println(knapsack(wt,val,s,0));
	System.out.println(knapsackTD(wt, val, s, 0, new int[wt.length][s + 1]));
}

public static int knapsack(int[] wt, int[] cost, int cap, int i) {

	if (cap == 0 || i == wt.length) {
		return 0;
	}

	int ans = 0;
	if (wt[i] > cap) {
		ans = knapsack(wt, cost, cap, i + 1);
	} else {
		int o1 = cost[i] + knapsack(wt, cost, cap - wt[i], i + 1);
		int o2 = knapsack(wt, cost, cap, i + 1);

		ans = Math.max(o1, o2);
	}

	return ans;
}

public static int knapsackTD(int[] wt, int[] cost, int cap, int i, int[][] strg) {

	if (cap == 0 || i == wt.length) {
		return 0;
	}

	if (strg[i][cap] != 0) {
		return strg[i][cap];
	}

	int ans = 0;
	if (wt[i] > cap) {
		ans = knapsackTD(wt, cost, cap, i + 1,strg);
	} else {
		int o1 = cost[i] + knapsackTD(wt, cost, cap - wt[i], i + 1,strg);
		int o2 = knapsackTD(wt, cost, cap, i + 1,strg);

		ans = Math.max(o1, o2);
	}

	strg[i][cap] = ans;

	return ans;
}

}

#6

It won’t give TLE
Just submit

1 Like