### krish2004's blog

By krish2004, history, 3 weeks ago,

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 ?

• -24

 » 3 weeks ago, # |   -19 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: def lis_recursive(nums, prev_idx, current_idx): if current_idx == len(nums): return 0 taken = 0 if prev_idx < 0 or nums[current_idx] > nums[prev_idx]: taken = 1 + lis_recursive(nums, current_idx, current_idx + 1) not_taken = lis_recursive(nums, prev_idx, current_idx + 1) return max(taken, not_taken) nums = [10, 22, 9, 33, 21, 50, 41, 60] print(lis_recursive(nums, -1, 0)) # Output: 5 (for LIS [10, 22, 33, 50, 60])  Add Memoization: Improve efficiency by memoizing results to avoid redundant calculations: memo = {} def lis_memo(nums, prev_idx, current_idx): if (prev_idx, current_idx) in memo: return memo[(prev_idx, current_idx)] if current_idx == len(nums): return 0 taken = 0 if prev_idx < 0 or nums[current_idx] > nums[prev_idx]: taken = 1 + lis_memo(nums, current_idx, current_idx + 1) not_taken = lis_memo(nums, prev_idx, current_idx + 1) memo[(prev_idx, current_idx)] = max(taken, not_taken) return memo[(prev_idx, current_idx)] nums = [10, 22, 9, 33, 21, 50, 41, 60] print(lis_memo(nums, -1, 0)) # Output: 5 (for LIS [10, 22, 33, 50, 60])  Transition to Tabulation: Solve iteratively using a bottom-up approach: def lis_tabulation(nums): if not nums: return 0 n = len(nums) dp = [1] * n for i in range(1, n): for j in range(0, i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) nums = [10, 22, 9, 33, 21, 50, 41, 60] print(lis_tabulation(nums)) # Output: 5 (for LIS [10, 22, 33, 50, 60])  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.