Adding memoization or tabulation for the state
This is the easiest part of a dynamic programming solution. We just need to store the state answer so that the next time that state is required, we can directly use it from our memory.
Adding memoization to the above code
C++
// initialize to -1int dp[MAXN];// this function returns the number of // arrangements to form 'n' int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; // checking if already calculated if (dp[n]!=-1) return dp[n]; // storing the result and returning return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);} |
Java
// initialize to -1public static int[] dp = new int[MAXN];// this function returns the number of // arrangements to form 'n' static int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; // checking if already calculated if (dp[n]!=-1) return dp[n]; // storing the result and returning return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);}// This code is contributed by Dharanendra L V. |
Python3
# This function returns the number of# arrangements to form 'n'# lookup dictionary/hashmap is initializeddef solve(n, lookup = {}): # Base cases # negative number can't be # produced, return 0 if n < 0: return 0 # 0 can be produced by not # taking any number whereas # 1 can be produced by just taking 1 if n == 0: return 1 # Checking if number of way for # producing n is already calculated # or not if calculated, return that, # otherwise calculate and then return if n not in lookup: lookup[n] = (solve(n - 1) + solve(n - 3) + solve(n - 5)) return lookup[n]# This code is contributed by GauriShankarBadola |
C#
// initialize to -1public static int[] dp = new int[MAXN];// this function returns the number of // arrangements to form 'n' static int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; // checking if already calculated if (dp[n]!=-1) return dp[n]; // storing the result and returning return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);}// This code is contributed by Dharanendra L V. |
Javascript
<script>// initialize to -1let dp = new Array(MAXN);// this function returns the number of// arrangements to form 'n'function solve(n){ // base case if (n < 0) return 0; if (n == 0) return 1; // checking if already calculated if (dp[n]!=-1) return dp[n]; // storing the result and returning return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);}// This code is contributed by avanitrachhadiya2155</script> |
Time Complexity: O(n), As we just need to make 3n function calls and there will be no repetitive calculations as we are returning previously calculated results.
Auxiliary Space: O(n), The extra space is used due to the recursion call stack.
Another way is to add tabulation and make the solution iterative. Please refer to tabulation and memoization for more details.
Dynamic Programming comes with lots of practice. One must try solving various classic DP problems that can be found here.
You may check the below problems first and try solving them using the above-described steps:-
|
S. No. |
Problem |
Practice link |
|
1 |
||
|
2 |
||
|
3 |
||
|
4 |
||
|
5 |
Contact Us