I have trying to solve a lot of DP problem but I feel stuck. I can solve most of greedy problem. Any advice

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 210 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 172 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

I have trying to solve a lot of DP problem but I feel stuck. I can solve most of greedy problem. Any advice

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 06:50:51 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

If you are beginner in DP , I would suggest you practice Recursive DP first. Almost all DP problems you see until 1700-1800 rating can be easily solved with recursive version.

Still if you want to learn iterative, I think writing the transitions on paper helps a lot.

For example, Suppose recursive version is,

inside func(i,j):

DP[i][j] = func(i+1,j+1) + func(i+2,j+1);

I generally convert that right most term into i... like

DP[i-2][j-1] = func(i-1,j) + func(i,j);

=> DP[i-2][j-1] = DP[i-1][j] + DP[i][j]

=>

DP[i][j] = DP[i-2][j-1] -DP[i-1][j]Now I have a formula to use iterative dp using for loop.

PS:This is just personal opinion. There may be better way to figure out transitions. But I learnt it this way. :P

thank you so much for replying. really appreciate. I will try them in recursion.Before I was only trying iterative.

Add Ashishgup to your friendlist and refer his solutions for problems you are trying to solve. He almost always solves using recursive and you can see his solutions to learn.

Okay I will. I did