Formulating a relation among the states
This part is the hardest part of solving a Dynamic Programming problem and requires a lot of intuition, observation, and practice.
Example:
Given 3 numbers {1, 3, 5}, The task is to tell the total number of ways we can form a number N using the sum of the given three numbers. (allowing repetitions and different arrangements).
The total number of ways to form 6 is: 8
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
The steps to solve the given problem will be:
- We decide a state for the given problem.
- We will take a parameter N to decide the state as it uniquely identifies any subproblem.
- DP state will look like state(N), state(N) means the total number of arrangements to form N by using {1, 3, 5} as elements. Derive a transition relation between any two states.
- Now, we need to compute state(N).
How to Compute the state?
As we can only use 1, 3, or 5 to form a given number N. Let us assume that we know the result for N = 1,2,3,4,5,6
Let us say we know the result for:
state (n = 1), state (n = 2), state (n = 3) ……… state (n = 6)
Now, we wish to know the result of the state (n = 7). See, we can only add 1, 3, and 5. Now we can get a sum total of 7 in the following 3 ways:
1) Adding 1 to all possible combinations of state (n = 6)
Eg : [ (1+1+1+1+1+1) + 1]
[ (1+1+1+3) + 1]
[ (1+1+3+1) + 1]
[ (1+3+1+1) + 1]
[ (3+1+1+1) + 1]
[ (3+3) + 1]
[ (1+5) + 1]
[ (5+1) + 1]2) Adding 3 to all possible combinations of state (n = 4);
[(1+1+1+1) + 3]
[(1+3) + 3]
[(3+1) + 3]3) Adding 5 to all possible combinations of state(n = 2)
[ (1+1) + 5](Note how it sufficient to add only on the right-side – all the add-from-left-side cases are covered, either in the same state, or another, e.g. [ 1+(1+1+1+3)] is not needed in state (n=6) because it’s covered by state (n = 4) [(1+1+1+1) + 3])
Now, think carefully and satisfy yourself that the above three cases are covering all possible ways to form a sum total of 7;
Therefore, we can say that result for
state(7) = state (6) + state (4) + state (2)
OR
state(7) = state (7-1) + state (7-3) + state (7-5)
In general,
state(n) = state(n-1) + state(n-3) + state(n-5)
Below is the implementation of the above approach:
C++
// Returns the number of arrangements to // form 'n' int solve(int n){ // base case if (n < 0) return 0; if (n == 0) return 1; return solve(n-1) + solve(n-3) + solve(n-5);} |
Java
// 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; return solve(n-1) + solve(n-3) + solve(n-5);} // This code is contributed by Dharanendra L V. |
Python3
# Returns the number of arrangements to # form 'n' def solve(n): # Base case if n < 0: return 0 if n == 0: return 1 return (solve(n - 1) + solve(n - 3) + solve(n - 5))# This code is contributed by GauriShankarBadola |
C#
// 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; return solve(n-1) + solve(n-3) + solve(n-5);} // This code is contributed by Dharanendra L V. |
Javascript
<script>// Returns the number of arrangements to // form 'n' function solve(n){ // base case if (n < 0) return 0; if (n == 0) return 1; return solve(n-1) + solve(n-3) + solve(n-5);} // This Code is Contributed by Harshit Srivastava</script> |
Time Complexity: O(3N), As at every stage we need to take three decisions and the height of the tree will be of the order of n.
Auxiliary Space: O(N), The extra space is used due to the recursion call stack.
The above code seems exponential as it is calculating the same state again and again. So, we just need to add memoization.
Contact Us