어레이의 최소 조정 비용 찾기
GfG Practice에서 사용해 보세요. 
#practiceLinkDiv { 표시: 없음 !중요; }
산출
#practiceLinkDiv { 표시: 없음 !중요; } 양의 정수 배열이 주어지면 배열의 인접한 요소 간의 차이가 주어진 목표보다 작거나 같도록 배열의 각 요소를 바꿉니다. 새 값과 기존 값의 차이를 합한 조정 비용을 최소화해야 합니다. 기본적으로 ?|A[i] - A를 최소화해야 합니다. 새로운 [나]| 어디 0? 나 ? n-1 n은 A[] 및 A의 크기입니다. 새로운 []는 인접 차이가 대상보다 작거나 같은 배열입니다. 배열의 모든 요소가 상수 M = 100보다 작다고 가정합니다.
예:
Input: arr = [1 3 0 3] target = 1
Output: Minimum adjustment cost is 3
Explanation: One of the possible solutions
is [2 3 2 3]
Input: arr = [2 3 2 3] target = 1
Output: Minimum adjustment cost is 0
Explanation: All adjacent elements in the input
array are already less than equal to given target
Input: arr = [55 77 52 61 39 6
25 60 49 47] target = 10
Output: Minimum adjustment cost is 75
Explanation: One of the possible solutions is
[55 62 52 49 39 29 30 40 49 47]
Recommended Practice 어레이의 최소 조정 비용 찾기 시도해 보세요!조정 비용을 최소화하기 위해 ?|A[i] - A 새로운 [나]| 배열의 모든 인덱스 i에 대해 |A[i] - A 새로운 [나]| 가능한 한 0에 가까워야 합니다. 또한 |A[i] - A 새로운 [i+1] ]| ? 목표.
이 문제는 다음과 같이 해결될 수 있습니다. 동적 프로그래밍 .dp[i][j]가 A[i]를 j로 변경할 때 최소 조정 비용을 정의하면 DP 관계는 다음과 같이 정의됩니다.
dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
for all k's such that |k - j| ? target
여기 0? 나 ? n과 0? j? M 여기서 n은 배열의 요소 수이고 M = 100입니다. max(j - target 0)이 되도록 모든 k를 고려해야 합니다. 케이? min(M j + 목표)
마지막으로 배열의 최소 조정 비용은 모든 0에 대해 min{dp[n - 1][j]}가 됩니다. j? 중.연산:
- A[i]를 j로 변경하는 데 따른 최소 조정 비용을 기록하기 위해 dp[n][M+1] 초기화를 사용하여 2D 배열을 만듭니다. 여기서 n은 배열의 길이이고 M은 최대값입니다.
- dp[0][j] = abs (j - A[0]) 공식을 사용하여 배열 dp[0][j]의 첫 번째 요소에 대해 A[0]을 j로 변경하는 데 필요한 최소 조정 비용을 계산합니다.
- 나머지 배열 요소 dp[i][j]에서 A[i]를 j로 바꾸고 공식 dp[i][j] = min(dp[i-1][k] + abs(A[i] - j))를 사용합니다. 여기서 k는 최소 조정 비용을 얻기 위해 max(j-target0)과 min(Mj+target) 사이에서 가능한 모든 값을 취합니다.
- 최소 조정 비용은 dp 테이블의 마지막 행에서 가장 낮은 숫자를 지정합니다.
다음은 위의 아이디어를 구현한 것입니다.
C++ // C++ program to find minimum adjustment cost of an array #include using namespace std ; #define M 100 // Function to find minimum adjustment cost of an array int minAdjustmentCost ( int A [] int n int target ) { // dp[i][j] stores minimal adjustment cost on changing // A[i] to j int dp [ n ][ M + 1 ]; // handle first element of array separately for ( int j = 0 ; j <= M ; j ++ ) dp [ 0 ][ j ] = abs ( j - A [ 0 ]); // do for rest elements of the array for ( int i = 1 ; i < n ; i ++ ) { // replace A[i] to j and calculate minimal adjustment // cost dp[i][j] for ( int j = 0 ; j <= M ; j ++ ) { // initialize minimal adjustment cost to INT_MAX dp [ i ][ j ] = INT_MAX ; // consider all k such that k >= max(j - target 0) and // k <= min(M j + target) and take minimum for ( int k = max ( j - target 0 ); k <= min ( M j + target ); k ++ ) dp [ i ][ j ] = min ( dp [ i ][ j ] dp [ i - 1 ][ k ] + abs ( A [ i ] - j )); } } // return minimum value from last row of dp table int res = INT_MAX ; for ( int j = 0 ; j <= M ; j ++ ) res = min ( res dp [ n - 1 ][ j ]); return res ; } // Driver Program to test above functions int main () { int arr [] = { 55 77 52 61 39 6 25 60 49 47 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int target = 10 ; cout < < 'Minimum adjustment cost is ' < < minAdjustmentCost ( arr n target ) < < endl ; return 0 ; }
Java // Java program to find minimum adjustment cost of an array import java.io.* ; import java.util.* ; class GFG { public static int M = 100 ; // Function to find minimum adjustment cost of an array static int minAdjustmentCost ( int A [] int n int target ) { // dp[i][j] stores minimal adjustment cost on changing // A[i] to j int [][] dp = new int [ n ][ M + 1 ] ; // handle first element of array separately for ( int j = 0 ; j <= M ; j ++ ) dp [ 0 ][ j ] = Math . abs ( j - A [ 0 ] ); // do for rest elements of the array for ( int i = 1 ; i < n ; i ++ ) { // replace A[i] to j and calculate minimal adjustment // cost dp[i][j] for ( int j = 0 ; j <= M ; j ++ ) { // initialize minimal adjustment cost to INT_MAX dp [ i ][ j ] = Integer . MAX_VALUE ; // consider all k such that k >= max(j - target 0) and // k <= min(M j + target) and take minimum int k = Math . max ( j - target 0 ); for ( ; k <= Math . min ( M j + target ); k ++ ) dp [ i ][ j ] = Math . min ( dp [ i ][ j ] dp [ i - 1 ][ k ] + Math . abs ( A [ i ] - j )); } } // return minimum value from last row of dp table int res = Integer . MAX_VALUE ; for ( int j = 0 ; j <= M ; j ++ ) res = Math . min ( res dp [ n - 1 ][ j ] ); return res ; } // Driver program public static void main ( String [] args ) { int arr [] = { 55 77 52 61 39 6 25 60 49 47 }; int n = arr . length ; int target = 10 ; System . out . println ( 'Minimum adjustment cost is ' + minAdjustmentCost ( arr n target )); } } // This code is contributed by Pramod Kumar
Python3 # Python3 program to find minimum # adjustment cost of an array M = 100 # Function to find minimum # adjustment cost of an array def minAdjustmentCost ( A n target ): # dp[i][j] stores minimal adjustment # cost on changing A[i] to j dp = [[ 0 for i in range ( M + 1 )] for i in range ( n )] # handle first element # of array separately for j in range ( M + 1 ): dp [ 0 ][ j ] = abs ( j - A [ 0 ]) # do for rest elements # of the array for i in range ( 1 n ): # replace A[i] to j and # calculate minimal adjustment # cost dp[i][j] for j in range ( M + 1 ): # initialize minimal adjustment # cost to INT_MAX dp [ i ][ j ] = 100000000 # consider all k such that # k >= max(j - target 0) and # k <= min(M j + target) and # take minimum for k in range ( max ( j - target 0 ) min ( M j + target ) + 1 ): dp [ i ][ j ] = min ( dp [ i ][ j ] dp [ i - 1 ][ k ] + abs ( A [ i ] - j )) # return minimum value from # last row of dp table res = 10000000 for j in range ( M + 1 ): res = min ( res dp [ n - 1 ][ j ]) return res # Driver Code arr = [ 55 77 52 61 39 6 25 60 49 47 ] n = len ( arr ) target = 10 print ( 'Minimum adjustment cost is' minAdjustmentCost ( arr n target ) sep = ' ' ) # This code is contributed # by sahilshelangia
C# // C# program to find minimum adjustment // cost of an array using System ; class GFG { public static int M = 100 ; // Function to find minimum adjustment // cost of an array static int minAdjustmentCost ( int [] A int n int target ) { // dp[i][j] stores minimal adjustment // cost on changing A[i] to j int [] dp = new int [ n M + 1 ]; // handle first element of array // separately for ( int j = 0 ; j <= M ; j ++ ) dp [ 0 j ] = Math . Abs ( j - A [ 0 ]); // do for rest elements of the array for ( int i = 1 ; i < n ; i ++ ) { // replace A[i] to j and calculate // minimal adjustment cost dp[i][j] for ( int j = 0 ; j <= M ; j ++ ) { // initialize minimal adjustment // cost to INT_MAX dp [ i j ] = int . MaxValue ; // consider all k such that // k >= max(j - target 0) and // k <= min(M j + target) and // take minimum int k = Math . Max ( j - target 0 ); for ( ; k <= Math . Min ( M j + target ); k ++ ) dp [ i j ] = Math . Min ( dp [ i j ] dp [ i - 1 k ] + Math . Abs ( A [ i ] - j )); } } // return minimum value from last // row of dp table int res = int . MaxValue ; for ( int j = 0 ; j <= M ; j ++ ) res = Math . Min ( res dp [ n - 1 j ]); return res ; } // Driver program public static void Main () { int [] arr = { 55 77 52 61 39 6 25 60 49 47 }; int n = arr . Length ; int target = 10 ; Console . WriteLine ( 'Minimum adjustment' + ' cost is ' + minAdjustmentCost ( arr n target )); } } // This code is contributed by Sam007.
JavaScript < script > // Javascript program to find minimum adjustment cost of an array let M = 100 ; // Function to find minimum adjustment cost of an array function minAdjustmentCost ( A n target ) { // dp[i][j] stores minimal adjustment cost on changing // A[i] to j let dp = new Array ( n ); for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ); for ( let j = 0 ; j <= M ; j ++ ) { dp [ i ][ j ] = 0 ; } } // handle first element of array separately for ( let j = 0 ; j <= M ; j ++ ) dp [ 0 ][ j ] = Math . abs ( j - A [ 0 ]); // do for rest elements of the array for ( let i = 1 ; i < n ; i ++ ) { // replace A[i] to j and calculate minimal adjustment // cost dp[i][j] for ( let j = 0 ; j <= M ; j ++ ) { // initialize minimal adjustment cost to INT_MAX dp [ i ][ j ] = Number . MAX_VALUE ; // consider all k such that k >= max(j - target 0) and // k <= min(M j + target) and take minimum let k = Math . max ( j - target 0 ); for ( ; k <= Math . min ( M j + target ); k ++ ) dp [ i ][ j ] = Math . min ( dp [ i ][ j ] dp [ i - 1 ][ k ] + Math . abs ( A [ i ] - j )); } } // return minimum value from last row of dp table let res = Number . MAX_VALUE ; for ( let j = 0 ; j <= M ; j ++ ) res = Math . min ( res dp [ n - 1 ][ j ]); return res ; } let arr = [ 55 77 52 61 39 6 25 60 49 47 ]; let n = arr . length ; let target = 10 ; document . write ( 'Minimum adjustment cost is ' + minAdjustmentCost ( arr n target )); // This code is contributed by decode2207. < /script>
PHP // PHP program to find minimum // adjustment cost of an array $M = 100 ; // Function to find minimum // adjustment cost of an array function minAdjustmentCost ( $A $n $target ) { // dp[i][j] stores minimal // adjustment cost on changing // A[i] to j global $M ; $dp = array ( array ()); // handle first element // of array separately for ( $j = 0 ; $j <= $M ; $j ++ ) $dp [ 0 ][ $j ] = abs ( $j - $A [ 0 ]); // do for rest // elements of the array for ( $i = 1 ; $i < $n ; $i ++ ) { // replace A[i] to j and // calculate minimal adjustment // cost dp[i][j] for ( $j = 0 ; $j <= $M ; $j ++ ) { // initialize minimal adjustment // cost to INT_MAX $dp [ $i ][ $j ] = PHP_INT_MAX ; // consider all k such that // k >= max(j - target 0) and // k <= min(M j + target) and // take minimum for ( $k = max ( $j - $target 0 ); $k <= min ( $M $j + $target ); $k ++ ) $dp [ $i ][ $j ] = min ( $dp [ $i ][ $j ] $dp [ $i - 1 ][ $k ] + abs ( $A [ $i ] - $j )); } } // return minimum value // from last row of dp table $res = PHP_INT_MAX ; for ( $j = 0 ; $j <= $M ; $j ++ ) $res = min ( $res $dp [ $n - 1 ][ $j ]); return $res ; } // Driver Code $arr = array ( 55 77 52 61 39 6 25 60 49 47 ); $n = count ( $arr ); $target = 10 ; echo 'Minimum adjustment cost is ' minAdjustmentCost ( $arr $n $target ); // This code is contributed by anuj_67. ?>
산출
Minimum adjustment cost is 75
시간 복잡도: O(n*m 2 )
보조 공간: O(n*m)
효율적인 접근 방식: 공간 최적화
이전 접근 방식에서는 현재 값 dp[i][j] 현재 및 이전 행 값에만 의존합니다. DP . 따라서 공간 복잡성을 최적화하기 위해 단일 1D 배열을 사용하여 계산을 저장합니다.
구현 단계:
- 1D 벡터 만들기 DP 크기의 m+1 .
- 값을 초기화하여 기본 사례를 설정합니다. DP .
- 이제 중첩 루프를 사용하여 하위 문제를 반복하고 이전 계산에서 현재 값을 가져옵니다.
- 이제 임시 1D 벡터를 만듭니다. prev_dp 이전 계산의 현재 값을 저장하는 데 사용됩니다.
- 매 반복 후에 다음 값을 할당합니다. prev_dp 추가 반복을 위해 dp로 이동합니다.
- 변수 초기화 입술 최종 답변을 저장하고 Dp를 반복하여 업데이트합니다.
- 마지막으로 저장된 최종 답변을 반환하고 인쇄합니다. 입술 .
구현:
#include using namespace std ; #define M 100 // Function to find minimum adjustment cost of an array int minAdjustmentCost ( int A [] int n int target ) { int dp [ M + 1 ]; // Array to store the minimum adjustment costs for each value for ( int j = 0 ; j <= M ; j ++ ) dp [ j ] = abs ( j - A [ 0 ]); // Initialize the first row with the absolute differences for ( int i = 1 ; i < n ; i ++ ) // Iterate over the array elements { int prev_dp [ M + 1 ]; memcpy ( prev_dp dp sizeof ( dp )); // Store the previous row's minimum costs for ( int j = 0 ; j <= M ; j ++ ) // Iterate over the possible values { dp [ j ] = INT_MAX ; // Initialize the current value with maximum cost // Find the minimum cost by considering the range of previous values for ( int k = max ( j - target 0 ); k <= min ( M j + target ); k ++ ) dp [ j ] = min ( dp [ j ] prev_dp [ k ] + abs ( A [ i ] - j )); } } int res = INT_MAX ; for ( int j = 0 ; j <= M ; j ++ ) res = min ( res dp [ j ]); // Find the minimum cost in the last row return res ; // Return the minimum adjustment cost } int main () { int arr [] = { 55 77 52 61 39 6 25 60 49 47 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int target = 10 ; cout < < 'Minimum adjustment cost is ' < < minAdjustmentCost ( arr n target ) < < endl ; return 0 ; }
Java import java.util.Arrays ; public class MinimumAdjustmentCost { static final int M = 100 ; // Function to find the minimum adjustment cost of an array static int minAdjustmentCost ( int [] A int n int target ) { int [] dp = new int [ M + 1 ] ; // Initialize the first row with absolute differences for ( int j = 0 ; j <= M ; j ++ ) { dp [ j ] = Math . abs ( j - A [ 0 ] ); } // Iterate over the array elements for ( int i = 1 ; i < n ; i ++ ) { int [] prev_dp = Arrays . copyOf ( dp dp . length ); // Store the previous row's minimum costs // Iterate over the possible values for ( int j = 0 ; j <= M ; j ++ ) { dp [ j ] = Integer . MAX_VALUE ; // Initialize the current value with maximum cost // Find the minimum cost by considering the range of previous values for ( int k = Math . max ( j - target 0 ); k <= Math . min ( M j + target ); k ++ ) { dp [ j ] = Math . min ( dp [ j ] prev_dp [ k ] + Math . abs ( A [ i ] - j )); } } } int res = Integer . MAX_VALUE ; for ( int j = 0 ; j <= M ; j ++ ) { res = Math . min ( res dp [ j ] ); // Find the minimum cost in the last row } return res ; // Return the minimum adjustment cost } public static void main ( String [] args ) { int [] arr = { 55 77 52 61 39 6 25 60 49 47 }; int n = arr . length ; int target = 10 ; System . out . println ( 'Minimum adjustment cost is ' + minAdjustmentCost ( arr n target )); } }
Python3 def min_adjustment_cost ( A n target ): M = 100 dp = [ 0 ] * ( M + 1 ) # Initialize the first row of dp with absolute differences for j in range ( M + 1 ): dp [ j ] = abs ( j - A [ 0 ]) # Iterate over the array elements for i in range ( 1 n ): prev_dp = dp [:] # Store the previous row's minimum costs for j in range ( M + 1 ): dp [ j ] = float ( 'inf' ) # Initialize the current value with maximum cost # Find the minimum cost by considering the range of previous values for k in range ( max ( j - target 0 ) min ( M j + target ) + 1 ): dp [ j ] = min ( dp [ j ] prev_dp [ k ] + abs ( A [ i ] - j )) res = float ( 'inf' ) for j in range ( M + 1 ): res = min ( res dp [ j ]) # Find the minimum cost in the last row return res if __name__ == '__main__' : arr = [ 55 77 52 61 39 6 25 60 49 47 ] n = len ( arr ) target = 10 print ( 'Minimum adjustment cost is' min_adjustment_cost ( arr n target ))
C# using System ; class Program { const int M = 100 ; // Function to find minimum adjustment cost of an array static int MinAdjustmentCost ( int [] A int n int target ) { int [] dp = new int [ M + 1 ]; // Array to store the minimum adjustment costs for each value for ( int j = 0 ; j <= M ; j ++ ) { dp [ j ] = Math . Abs ( j - A [ 0 ]); // Initialize the first row with the absolute differences } for ( int i = 1 ; i < n ; i ++ ) // Iterate over the array elements { int [] prevDp = ( int []) dp . Clone (); // Store the previous row's minimum costs for ( int j = 0 ; j <= M ; j ++ ) // Iterate over the possible values { dp [ j ] = int . MaxValue ; // Initialize the current value with maximum cost // Find the minimum cost by considering the range of previous values for ( int k = Math . Max ( j - target 0 ); k <= Math . Min ( M j + target ); k ++ ) { dp [ j ] = Math . Min ( dp [ j ] prevDp [ k ] + Math . Abs ( A [ i ] - j )); } } } int res = int . MaxValue ; for ( int j = 0 ; j <= M ; j ++ ) { res = Math . Min ( res dp [ j ]); // Find the minimum cost in the last row } return res ; // Return the minimum adjustment cost } static void Main () { int [] arr = { 55 77 52 61 39 6 25 60 49 47 }; int n = arr . Length ; int target = 10 ; Console . WriteLine ( 'Minimum adjustment cost is ' + MinAdjustmentCost ( arr n target )); } }
JavaScript const M = 100 ; // Function to find minimum adjustment cost of an array function minAdjustmentCost ( A n target ) { let dp = new Array ( M + 1 ); // Array to store the minimum adjustment costs for each value for ( let j = 0 ; j <= M ; j ++ ) dp [ j ] = Math . abs ( j - A [ 0 ]); // Initialize the first row with the absolute differences for ( let i = 1 ; i < n ; i ++ ) // Iterate over the array elements { let prev_dp = [... dp ]; // Store the previous row's minimum costs for ( let j = 0 ; j <= M ; j ++ ) // Iterate over the possible values { dp [ j ] = Number . MAX_VALUE ; // Initialize the current value with maximum cost // Find the minimum cost by considering the range of previous values for ( let k = Math . max ( j - target 0 ); k <= Math . min ( M j + target ); k ++ ) dp [ j ] = Math . min ( dp [ j ] prev_dp [ k ] + Math . abs ( A [ i ] - j )); } } let res = Number . MAX_VALUE ; for ( let j = 0 ; j <= M ; j ++ ) res = Math . min ( res dp [ j ]); // Find the minimum cost in the last row return res ; // Return the minimum adjustment cost } let arr = [ 55 77 52 61 39 6 25 60 49 47 ]; let n = arr . length ; let target = 10 ; console . log ( 'Minimum adjustment cost is ' + minAdjustmentCost ( arr n target )); // This code is contributed by Kanchan Agarwal
산출
Minimum adjustment cost is 75
시간 복잡도: O(n*m 2 )
보조 공간: 오(m)
