Rough Approach of DP problem types 🤔

The problem can be of two types:

1. like in permutation I can only choose 1 element from 1 row
2. or I can choose 1 element 'SEVERAL' no. of times

---

1.🔶 can only choose 1 element from 1 row

Question might have asked:

✅min or max AMOUNT

the dp(_,_) function returns the AMOUNT

info

This return AMOUNT is determined by the base case like:

if (row == C)
    return M - budget; // budget is remaining budget

• need to have a 2D vector/array to store row & their col
• create row as one of the states
• for each recursive step make row+1
• have another state
• then in each row choose the 1 element/col you want as per problem & make required changes to the OTHER state

  always use min(_,_,_) or max(_,_,_) to get OPTIMAL Solution in EACH step

---

2.🔶 can choose 1 element SEVERAL no. of times

Question might have asked:

✅min or max no. of steps taken to reach Optimal Solution

the dp() function returns the COUNT of steps

info

This return AMOUNT is determined by the base case like:

if (total == 0) return 0; // here total is total Coins
// as total coins is `0`, so the no. of steps taken is also `0`

• no need to make any row state : as all the elements can be chosen multiple times, no point in creating row
• always choose each element

  always use min(_,_,_) or max(_,_,_) to get OPTIMAL Solution in EACH step

• to COUNT steps just add +1 to the the dp(_) function call like dp(_) + 1

  ans = min(ans, dp(x-c)+1);

---