재미있는 제목.

이것은 한 무리의 신이 나에게 낸 것이다. 제목은 주사위를 던지는 것이다. 한 체에 15번을 던지고 숫자가 50인 모든 가능한 숫자를 물어보자. 이 문제를 듣고 나는 먼저 DFS를 생각했다. 거슬러 올라가 가지치기를 했다. 그러나 그는 DP로도 할 수 있다고 말했다. DP에 대해 나의 이해는 매트릭스 곱셈에 있다. 마지막에 마지막 답안까지 미루었다. 그러나 그의 이 문제는 뚜렷하다. 50은 모든 조합의 가능성일 뿐이다.바로 밀어붙일 수는 없었는데 한참을 생각했지만 어떻게 해야 할지 몰랐다. 그는 나에게 상태 이동 방정식을 주었다. status[i][j]=status[i-1][k]를 더(k=1,2,3~~~~~~~~~~),status[i][j]는 i를 던질 때 누적과 합이 j라는 뜻이다.
나중에 나는 행렬을 그렸다. status[1][1]부터 분명히 첫 번째는 1-6, 여섯 가지 가능성이 있다. status[0][1]----status[0][6]는 모두 1이다. 그 다음에 두 번째 투구를 계산한다. 두 번째 투구할 때 그 경계를 고려해야 한다. 두 번째는 i이고 상계는 6*i이다. 각각 2,12이다. 그리고 이 범위에서 순서대로 데이터를 기입한다. 그리고 우리는 status[2][2]를 보면 이것은 한 가지 가능성만 있다. 첫 번째는 1이다.status[2][3], 분명히 두 가지만 가능(첫 번째 1, 두 번째 2, 또는 첫 번째 2, 두 번째 1), 이 숫자는 어떻게 계산합니까?우리는status[2][3]를 예로 들면 두 번째 투하, 화는 3이다. 여기는 앞의 두 번의 누적 합이 3이고 한 가지 뜻이 누설되었다. 첫 번째는 반드시 3, 1과 2보다 작아야 한다. 네가 선택하든지 네가 선택하든지 한 숫자만 선택하면 나는 대응하는 숫자를 너와 조합해서 3을 만들어야 한다. 이 말은 매우 중요하다. 이 말은 네가 j범위보다 작게 선택하든지 간에 반드시 하나의 숫자가 너와 3을 합쳐야 한다. 그래서전이방정식은 이전 줄의 j보다 작은 숫자를 모두 합친 것이다. 그러나 여기서 주의해야 한다. 여기는 상황을 나누어야 한다. status[2][8]를 보면 여기는 8을 나타낸다. 그러면 첫 번째는 1이면 두 번째는 아무리 던져도 8의 상황이 나타나지 않을 것이다. 그래서 여기는 이전 줄의 8-6, 즉 j=2의 부분부터 뒤로 누적되고 status[2]를 보면 1의 부분부터 누적되기 때문에 조건 판단을 해야 한다.현재 j가status[i-1][i+6]보다 작으면status[i-1][2*i]부터 뒤로 누적되기 때문에 여기서 판단을 해야 한다.
코드는 다음과 같다.
    

//    15   50     
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
long long dp[MAXSIZE][MAXSIZE];
void Cal(int len)
{ 
	memset(dp,0,sizeof(dp));
	int i,j,k;
	for(i=1;i<=6;i++)
	{
	  dp[1][i]=1;
	}
	for(i=2;i<=len;i++)
	{
      	for(j=i;j<=6*i;j++)
		{
		  if(j<=(i-1+6))
		  {
		     for(k=i-1;k<j;k++)
			 {
			   dp[i][j]+=dp[i-1][k];
			 }
		  }
		  else
		  {
		     for(k=j-6;k<j;k++)
			 {
			   dp[i][j]+=dp[i-1][k];
			 }
		  }
		}
	}


}
int main()
{
	int i,j;
  Cal(15);
  printf("%d
",dp[15][50]);
 return 0;
}