leetcode 검 은 offer 면접 문제 60. n 주사위 의 포 인 트 를 가리킨다.

문제: n 개의 주사 위 를 바닥 에 던 지고 모든 주사 위 는 위 를 향 한 포인트 의 합 은 s 이다.n 을 입력 하면 s 의 모든 가능 한 값 이 나타 날 확률 을 출력 합 니 다.너 는 부동 소수점 배열 로 답 을 되 돌려 야 한다. 그 중에서 i 번 째 요 소 는 n 개의 주사위 가 던 질 수 있 는 포인트 집합 에서 i 번 째 작은 확률 을 대표 한다.
   1:
  : 1
  : [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

   2:
  : 2
  : [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

제한: 1 < = n < = 11
문제 풀이 방향: 1. 확률 이 있 을 수 있 습 니 다 = 값 이 나타 난 횟수 / 총 횟수;총 횟수 = pow (6, n) 2. 2 차원 배열 dp [i] [j] 를 신청 하면 i 개의 주사위 가 j 가 나타 날 만 한 횟수 상태 로 방정식 을 이전 할 수 있다 는 뜻 이다. 모두 n 개의 주사위, 마지막 주사 위 를 던 진 후에 dp [n] [j] 로 n 개의 주사위 가 j 를 던 진 횟수 를 나타 내 면 n - 1 개의 주사위 가 던 진 후에 해당 하 는 포 인 트 는 j - 1, j - 2, j - 3... j - 6 이 라 고 할 수 있다.있다:
for (i = 1; i <= 6; i++){
     
	dp[n][j] += dp[n - 1][j - i];
}

3. 주의해 야 할 것 은 주사위 가 하나 더 많 을 때마다 하나의 값 이 나타 나 지 않 는 다 는 것 이다. 예 를 들 어 두 개의 주사위 와 1 이 나타 나 지 않 는 다 는 것 이다. 적어도 2 이다.
코드 구현:
double* twoSum(int n, int* returnSize){
     
    int i, j, k;
    int len = 5 * n + 1;
    * returnSize = len;
    double* res = (double*)malloc(sizeof(double) * len);
    int dp[12][67] = {
     0};                //             n      j     
    for (i = 1; i <= 6; i++){
                        //               
        dp[1][i] = 1;
    }
    for (i = 2; i <= n; i++){
                        //        2 
        for (j = i; j <= 6 * i; j++){
                //          
            for (k = 1; k <= 6; k++){
                // n     6   
                if (j - k <= 0){
     
                    break;
                }
                //  n      k ,   n-1             
                dp[i][j] += dp[i - 1][j - k];   
            }
        }
    }
    int all = pow(6, n);
    for (i = 0; i < len; i++){
     
        res[i] = dp[n][n + i] * 1.0 / all;
    }
    return res;
}

좋은 웹페이지 즐겨찾기