[점프형 dp] A015LC_DI 서열의 유효한 배열 (앞의 숫자에 따라 뒤의 숫자)
1. Problem
우리는 S, {'D', 'I'}에서 유래한 길이가 n인 문자열을 보여 줍니다.(이 문자들은'감소'와'증가'를 대표한다.)
유효한 배열은 정수 {0,1,...,n}에 대한 배열 P[0],P[1],...,P[n]로 모든 i에 대해
："DID"
：5
：
(0, 1, 2, 3) ：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)
팁:
1 <= S.length <= 200 S는 컬렉션 {"D", "I"}의 문자로만 구성됩니다.
2. 솔루션
방법1:dp
사색
이 문제는 승강과 관련이 있으니 적어도 두 차원은 있어야 한다.
그리고 한 서열에서 {0,..., i-2, i-1,i}, 뒷수 i는 틀림없이 앞의 수 i-1을 바탕으로 얻어진 것이고 뒷수의 선택은 여러 가지가 있을 수 있기 때문에 합법적인 숫자를 매거해야 한다.
마지막으로 끊임없이bottom-up이 교체되어 최종 결과를 얻었습니다.
사고의 방향
class Solution {
public:
int numPermsDISequence(string s) {
int n=s.size(), mod = 1e9+7, f[n+1][n+1]; memset(f, 0, sizeof f);
f[0][0]=1;
for (int i=1; i<=n; i++)
for (int j=0; j<=i; j++) {
if (s[i-1]=='D') for (int k=0; k<j; k++) {
f[i][j] = (f[i][j] + f[i-1][k]) % mod;
} else for (int k=j; k<=i; k++) {
f[i][j] = (f[i][j] + f[i-1][k]) % mod;
}
}
int ans=0;
for (int v : f[n]) ans=(ans+v)%mod;
return ans;
}
};
복잡도 분석
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
