[LintCode] k Sum
3817 단어 code
Find k numbers where sum is target. Calculate how many solutions there are?
Example
Given [1,2,3,4], k=2, target=5. There are 2 solutions:
[1,4] and [2,3], return 2.
http://www.lintcode.com/en/problem/k-sum/
dp[k][v]는 k개수와 v를 사용한 방안수를 나타낸다. 그러면 새로 추가된 개수 a에 대해 상태 이동 방정식은 다음과 같다.
dp[k][v] += dp[k-1][v-a];
다음은 AC 코드입니다.
1 class Solution {
2 public:
3 /**
4 * @param A: an integer array.
5 * @param k: a positive integer (k <= length(A))
6 * @param target: a integer
7 * @return an integer
8 */
9
10 int kSum(vector<int> A, int k, int target) {
11 // wirte your code here
12 vector<vector<int> > dp(k + 1, vector<int>(target + 1, 0));
13 dp[0][0] = 1;
14 for (auto a : A) {
15 for (int kk = k; kk > 0; --kk) {
16 for (int v = target; v >= a; --v) {
17 dp[kk][v] += dp[kk-1][v - a];
18 }
19 }
20 }
21 return dp[k][target];
22 }
23 };이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
소스 코드가 포함된 Python 프로젝트텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
