*Leetcode 813. Largest Sum of Averages | dp
1110 단어 DPLetCode 문제 풀이
의외로 n^2*kA를 떨어뜨릴 수 있다니...
class Solution {
public:
double largestSumOfAverages(vector& A, int K) {
int n = A.size();
if (n == 0) return 0;
double sum[n+1];
for (int i = 0; i < n; i++) {
sum[i] = i == 0? A[i] : sum[i-1] + A[i];
}
if (K >= n) {
return sum[n-1];
}
vector< vector >dp( A.size() + 1 , vector(K+1, 0.0) );
for (int i = 0; i < n; i++ ) {
for (int t = 1; t <= K; t++) {
for (int j = 0; j <= i; j++) { // j
if (t > i+1) continue;
if (t == 1 || j == 0 ) {
dp[i][t] = (sum[i] ) / (i +1);
continue;
}
dp[i][t] = max(dp[i][t], dp[j-1][t-1] + (sum[i] - sum[j-1]) / (i-j+1));
}
}
}
return dp[n-1][K];
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
