[Dp] DP에서 배열 사용

 + 이 글은 작성자가 직접 공부하고 복습하며 작성한 글입니다. 만약 직접 작성하지 않았다면, 꼭 출처를 밝히겠습니다!

 + 이 글은 개인적인 공부를 바탕으로 작성되었기에, 틀린 부분이 있을 수 있으며, 틀린 부분이 있다면 알려주시면 감사하겠습니다!

 + 이 글을 다른 곳으로 가져가신다면, 꼭 출처를 남겨주세요~

 + '참고사이트'는 공부하기 위해 참고한 사이트들을 모아 둔 것입니다.

  "DP문제에서 배열은 0번이 아닌 1번 부터 사용하자!!!"

 일반적으로 우리가 알고리즘 문제를 풀 때, 0부터 접근해서 반복문을 돌리던, 값을 바꾸던 한다. 
그러나 DP에서는 1부터 접근하는게 더 효율적이거나 가독성이 좋을 수 있다.

  일반적으로 DP는 점화식을 찾는 것부터 시작되는데, 이 점화식은 1번부터 시작하는 경우가 많다. 만약 이러한 경우에서 반복문을 0부터 돌리게 된다면, i + 1 이 기본 접근 방식이 되어 가독성이 떨어질 수 있을 뿐더러, i - 1번 째에 접근할 때, i가 0이라면 -1번째에 접근하게되 따로 예외처리를 해줘야 한다. 하지만 1번 부터 시작하게 된다면, 자연스럽게 i - 1이 0번째로가 다른 예외처리 없이 똑같이 끝까지 실행시킬 수 있다.

  보는 바와 같이 코드 길이 뿐 아니라 가독성에서도 차이가 확 벌어진다.

  따라서, DP문제에서 점화식을 찾았다면, 배열을 0이 아닌 1부터 사용하는 것이 좀 더 유용할 것이다.

---

** 참고사이트 **

 - Noting