How to approach problems for DP? and as a beginner should I start approaching the question in tabulation method or in recursive method and then change it to the tabulation method ?

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

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

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

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

How to approach problems for DP? and as a beginner should I start approaching the question in tabulation method or in recursive method and then change it to the tabulation method ?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 19:29:17 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Suggestion:-Don't cheat in any contest.-Challenge yourself with harder problems independently. If you encounter difficulties, start with a brute force approach. If it's inefficient (e.g., Time Limit Exceeded), then consider alternative strategies such as:— Mathematical optimizations — Implementation techniques like greedy algorithmsFor instance, when faced with a challenging problem like "Longest Increasing Subsequence (LIS)", you might initially attempt a brute force solution that checks all subsequences. However, this approach can become impractical for larger inputs. To optimize, you could implement a dynamic programming solution that uses memoization or tabulation to efficiently compute the LIS length in ( O(n^2) ) or ( O(n \log n) ) time complexity, respectively.

approach of the LIS problem using dynamic programming:

Understand the Problem: Given an array of integers, find the length of the longest increasing subsequence.Start with Recursive Approach: Begin by defining a recursive function to explore all subsequences:Add Memoization: Improve efficiency by memoizing results to avoid redundant calculations:Transition to Tabulation: Solve iteratively using a bottom-up approach:Practice and Compare: Solve other dynamic programming problems using both recursive with memoization and iterative tabulation approaches to understand their strengths and when to use each.Refine Solutions: Continuously review and optimize your solutions for clarity and efficiency based on problem requirements.