LeCalin's blog

Easy problem on DP
By LeCalin, history, 9 years ago, In English

Hello Codeforces .

Plase help.

Given n, array a(a1, a2,,, an). n, a[i] <= 100.

How can i make dp[i][j].

Corectly dp[i][j] = 1, if we can get sum j without a[i].

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

»
9 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

How can you say its easy if you are stuck in it and asking for help? :/

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    it is easy for some people

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I have thought of a solution.

      Take dpt[j] be the number of ways you can make the sum j using any elements. So, for each sum from 1 to 10000, you take each of the a[i] into consideration and do a dpt[sum-a[i]]++.

      Now, dp[i][j] is 1 if dpt[j]>=2 or else its 0.

      → Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What are the constraints on n ?

If you don't mind, can you put a link to the exact question. This is kind of hard to understand.

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Calculate DP for prefixes and suffixes. Now, DP[i][j] = 1 if there exists A and B such that A+B=j and A is obtained as sum from prefix and B is obtained as sum from suffix.

→ Reply