세 개의 정수 n, m, k가 있다고 가정합니다. 양의 정수 배열의 최대 요소를 찾는 다음 알고리즘이 있는 경우 -
max_val := -1 max_ind := -1 search_cost := 0 n := size of arr for initialize i := 0, when i < n, update (increase i by 1), do: if max_val < arr[i], then: max_val := arr[i] max_ind := i (increase search_cost by 1) return max_ind
다음 기준을 갖는 배열 arr을 만들어야 합니다. arr은 정확히 n개의 정수를 갖습니다. 모든 요소 arr[i]는 1에서 m(포함)(0 <=i
따라서 입력이 n =2, m =3, k =1과 같으면 가능한 배열이 [1, 1], [2, 1], [2, 2], [3이므로 출력은 6이 됩니다. , 1], [3, 2] [3, 3]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=10^9 + 7
-
add() 함수를 정의하면, b,
-
return ((a mod m) + (b mod m)) mod m
-
54 x 54 x 105 크기의 배열 dp를 정의합니다.
-
help() 함수를 정의하면 idx, m, k, currVal, n,
가 필요합니다. -
k <0이면 -
-
0 반환
-
-
idx가 n + 1과 같으면 -
-
k가 0일 때 true를 반환
-
-
dp[idx, k, currVal + 1]이 -1과 같지 않으면 -
-
반환 dp[idx, k, currVal + 1]
-
-
ret :=0
-
i:=1 초기화의 경우, i <=m일 때 업데이트(i를 1만큼 증가), −
-
i> currVal이면 -
-
ret :=add(help(idx + 1, m, k - 1, max(currVal,i), n), ret)
-
-
그렇지 않으면
-
ret :=add(help(idx + 1, m, k, max(currVal,i), n), ret)
-
-
-
반환 dp[idx, k, currVal + 1] =ret
-
주요 방법에서 다음을 수행하십시오 -
-
initialize i :=0의 경우, i <54일 때 업데이트(i를 1만큼 증가), 수행 -
-
initialize j :=0의 경우 j <54일 때 업데이트(j를 1만큼 증가), −
-
초기화 k :=0의 경우 k <105일 때 업데이트(k를 1만큼 증가), 수행 -
-
dp[i, j, k] :=-1
-
-
-
ret :=help(1, m, k, -1, n)
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public: lli add(lli a, lli b) { return ((a % m) + (b % m)) % m; } int dp[54][54][105]; int help(int idx, int m, int k, int currVal, int n) { if (k < 0) return 0; if (idx == n + 1) { return k == 0; } if (dp[idx][k][currVal + 1] != -1) return dp[idx][k][currVal + 1]; int ret = 0; for (int i = 1; i <= m; i++) { if (i > currVal) { ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret); } else { ret = add(help(idx + 1, m, k, max(currVal, i), n), ret); } } return dp[idx][k][currVal + 1] = ret; } int numOfArrays(int n, int m, int k) { for (int i = 0; i < 54; i++) for (int j = 0; j < 54; j++) for (int k = 0; k < 105; k++) dp[i][j][k] = -1; int ret = help(1, m, k, -1, n); return ret; } }; main() { Solution ob; cout << (ob.numOfArrays(2, 3, 1)); }
입력
2, 3, 1
출력
6