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 | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 162 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
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 ?
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 algorithms
For 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:
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.