673. 최장 증자 서열의 개수
1728 단어 DP
예1:
: [1,3,5,4,7]
: 2
: ， [1, 3, 4, 7] [1, 3, 5, 7]。
예2:
: [2,2,2,2,2]
: 5
: 1， 5 1， 5。
주의: 주어진 그룹의 길이는 2000을 넘지 않으며 결과는 32비트에 기호 정수가 있어야 합니다.
문제 해결 방법:
dp(n,1) cnt(n,1) 정의
여기에서 나는 dp[i]로nums[i]를 끝으로 하는 추이 서열의 길이를 표시하고, cnt[i]로nums[i]를 끝으로 하는 추이 서열의 개수를 표시하며, 초기화는 모두 1이다. 숫자만 있으면 적어도 1이다.그리고 우리는 모든 숫자nums[i]를 옮겨다니며, 모든 숫자nums[j]를 옮겨다니며,nums[i]가nums[j]보다 작을 때, 점증 서열이 아니기 때문에 아무런 처리도 하지 않습니다.반대로 dp[i]와 dp[j]의 관계를 판단한다. 만약에 dp[i]가 dp[j]+1과 같다면nums[i]라는 숫자는nums[j]로 끝나는 점증 서열 뒤에 추가할 수 있고nums[j]로 끝나는 점증 서열 개수는nums[i]로 끝나는 점증 서열 개수에 직접 추가할 수 있다.만약 dp[i]가 dp[j]+1보다 작다면 우리는 길이가 더 긴 증가 서열을 찾았다는 것을 의미한다. 그러면 우리는 이 때 dp[i]를 dp[j]+1으로 업데이트하고 원래의 증가 서열을 사용할 수 없으며 cnt[j]로 대체한다.전역에서 가장 긴 하위 시퀀스 길이 mx를 유지하고 매번 업데이트하며 마지막에 각 노드를 반복합니다. 만약 길이가 mx와res+=cnt[i]라면.
code:
class Solution {
public:
int findNumberOfLIS(vector& nums) {
int n = nums.size(), max_len = 1, res = 0;
vector dp(n, 1), cnt(n, 1); //dp i ，cnt i
for(int i = 1; i < n; ++i){
for(int j = 0; j < i; ++j){
if(nums[j] < nums[i] && dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
cnt[i] = cnt[j];
} else if(nums[j] < nums[i] && dp[j] + 1 == dp[i]){
cnt[i] += cnt[j];
}
}
max_len = max(max_len, dp[i]);
}
for(int i = 0; i < n; ++i)
if(dp[i] == max_len) res += cnt[i];
return res;
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
