[알고리즘]동적계획법-조약돌문제 구현

조약돌문제 점화식 표현 조약돌 문제에서 가장 중요한 조건은 우리가 놓은 조약돌이 인접하지 않게 놓는 것입니다. 조약돌이 놓일수 있는 경우의수를 확인해보고, 이를 패턴으로 정리해보겠습니다. [표]조약돌문제에서 조약돌을 놓을수있는는 패턴의 정의 패턴의 정의 4개의 패턴이 가능한것을 볼 수 있습니다. 첫번째 패턴에서 세번째 패턴은 각각의행에 조약돌을 놓는 패턴 입니다. 네번째패턴은 1번째 행과 3번째 행에 조약돌을 넣는 패턴 입니다. 첫번째 패턴뒤에 올수 있는패턴 첫번째 패턴과 각각의패턴이 결합한 모습입니다. {2,3}패턴은 인접하지 않으므로 가능 합니다. 하지만 {4}패턴은 첫번째 열이 겹치므로 불가능합니다. 두 번째 패턴뒤에 올수 있는패턴 두번째 패턴과 각각의패턴이 결합한 모습입니다. {1,3,4}패턴 모두 인접 하지 않으므로 가능합니다. 세 번째 패턴뒤에 올수 있는패턴 세번째 패턴과 각각의패턴이 결합한 모습입니다. {1,2}패턴은 인접하지 않으므로 가능 합니다. 하지만 {3,4}패턴...

원문링크 : [알고리즘]동적계획법-조약돌문제 구현