【LintCode】869. 하나의 그룹의 착란을 찾아내다 (동적 기획)
965 단어 LintCode
상태 설정: f[i]는 i개 요소를 포함하는 배열이 생성할 수 있는 착란의 수량을 나타낸다
상태 전이 방정식:
f[i] = (i - 1) * (f[i-1] + f[i-2])경계: f[1] = 0, f[2] = 1f[n]의 계산에 대해 n을 k번째 위치에 두었다고 가정하면 다음과 같다.k 모두 n-1개의 선택이 있기 때문
f[n] = (i - 1) * (f[n-1] + f[n-2])public class Solution {
/**
* @param n: an array consisting of n integers from 1 to n
* @return: the number of derangement it can generate
*/
public int findDerangement(int n) {
if (n <= 1) {
return 0;
}
long[] dp = new long[n + 1];
int mod = 1000000007;
dp[2] = 1;
for (int i=3; i < n + 1; i++) {
dp[i] = (long) (i - 1) * (dp[i-2] + dp[i-1]) % mod;
}
return (int)dp[n];
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
lintcode--94. 두 갈래 나무의 최대 경로와두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합) 두 갈래 나무 한 그루를 주시오. 되돌아오다 뒷순서에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
