when calculating the value of dp [i][][], just the value of dp[i — 1][][] is needed. Therefor you only need dp [2][][], where dp [0][][] is dp[i — 1] and dp[1][][] is dp [i][][] .Remember to swap them after each for loop