Dynamic Programming State Transitions
Welcome to the Dynamic Programming State Transitions visualization for n=3, k=2. We'll show how the values of same[i] and diff[i] progress from base cases through each iteration.
i
same[i]
diff[i]
Total ways
1
0
2
2
2
2
2
4
3
2
4
6
same[2] = diff[1] = 2
diff[2] = (k-1) × (same[1] + diff[1]) = 1 × (0 + 2) = 2
same[3] = diff[2] = 2
diff[3] = (k-1) × (same[2] + diff[2]) = 1 × (2 + 2) = 4
Step 1 of 6
Previous
Next