Nil_paracetamol's blog

Simple Dp Problem
By Nil_paracetamol, history, 4 years ago, In English

Problem Link

My solution

I've tried all test cases from uDebug and some random test case but could not find out wrong answer.

Is there any corner cases, which i've been not taking?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Not sure what your solution is or why are you taking max but i guess the solution should look something like this :

$$$dp[val][cnt] = \displaystyle\sum_{x=1}^{val} dp[val-x][cnt-1]$$$ with base case $$$dp[0][0] = 1$$$

Where $$$dp[i][j]$$$ means the number of ways to get sum $$$i$$$ with exactly $$$j$$$ coins. You can answer all the other types using these dp values.

→ Reply