Dynamic Programming Questions Medium
The time complexity of the Dynamic Programming approach for solving the House Robber problem is O(n), where n is the number of houses.
In the House Robber problem, we are given an array of non-negative integers representing the amount of money in each house. The goal is to determine the maximum amount of money we can rob without robbing adjacent houses.
To solve this problem using Dynamic Programming, we can use a bottom-up approach. We create an array dp of size n+1, where dp[i] represents the maximum amount of money that can be robbed from the first i houses.
We initialize dp[0] as 0 (no houses to rob) and dp[1] as the amount of money in the first house. Then, for each house from the second one onwards, we calculate dp[i] as the maximum of either robbing the current house and the amount of money in the house two steps back (dp[i-2] + nums[i]), or not robbing the current house and taking the maximum amount of money from the previous house (dp[i-1]).
By iterating through all the houses once, we can fill the dp array and determine the maximum amount of money that can be robbed from the given houses. Hence, the time complexity of this Dynamic Programming approach is O(n).