✔️ 출처쉬운 계단 수 실버 1 📖 문제중복 연산이 많이 일어나고 반복적이다. 이참에 다시 학교에서 배운 DP의 적용 요건을 복습하겠다. 최적 부분구조(Optimal substructure)큰 문제의 최적 해에 하위 문제의 최적 해가 포함하위 문제들의 중복 (overlapping recursive calls)재귀적 해법으로 풀면 같은 하위 문제에 대한 호출이 심하게 중복 재귀적으로 깊이만큼 0~9까지 +1 -1을 하면서 생성하다보면 엄청난 중복이 생김이전의 깊이에서 얻은 갯수를 재활용할 수 있을 것 같음. DP를 적용해보자 우선 0과 9는 1가지 밖에 없다.0 → 19 → 8따라서 0 과 9는 따로 처리하고 1~8까지는 -1 +1 숫자가 계단 수이니 이전 깊이의 -1 +1 숫자의 개수를 더한다. ..
