Here's a python program. Please rewrite it in c with the type signature float solve_dp(float* arr, int size, int lines_left) def solve_dp(graph, lines_left): n = len(graph) dp = [[[1e9 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] # Initialize how as -1 indicating no decision made how = [[[-1 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] for i in range(n, -1, -1): for j in range(lines_left + 1): for k in range(10): if i == n and j == 0: dp[i][j][k] = 0 else: # Option 1: don't take the line if i < n and k < 9: if dp[i + 1][j][k + 1] < dp[i][j][k]: dp[i][j][k] = dp[i + 1][j][k + 1] how[i][j][k] = k + 1 # Representing choosing not to take the line # Option 2: take the line if i < n and j > 0: cost = graph[i] + (k - 8)**2 if cost + dp[i + 1][j - 1][0] < dp[i][j][k]: dp[i][j][k] = cost + dp[i + 1][j - 1][0] how[i][j][k] = 0 # Representing choosing to take the line # Reconstruct the solution i, j, k = 0, lines_left, 6 taken_lines = [] while i < n: if how[i][j][k] == 0: # Chose to take the line taken_lines.append(n - i) i += 1 j -= 1 k = 0 else: # Chose not to take the line i += 1 k += 1 return dp[0][lines_left][6]
Here's a python program. Please rewrite it in c with the type signature float solve_dp(float* arr, int size, int lines_left) def solve_dp(graph, lines_left): n = len(graph) dp = [[[1e9 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] # Initialize how as -1 indicating no decision made how = [[[-1 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] for i in range(n, -1, -1): for j in range(lines_left + 1): for k in range(10): if i == n and j == 0: dp[i][j][k] = 0 else: # Option 1: don't take the line if i < n and k < 9: if dp[i + 1][j][k + 1] < dp[i][j][k]: dp[i][j][k] = dp[i + 1][j][k + 1] how[i][j][k] = k + 1 # Representing choosing not to take the line # Option 2: take the line if i < n and j > 0: cost = graph[i] + (k - 8)**2 if cost + dp[i + 1][j - 1][0] < dp[i][j][k]: dp[i][j][k] = cost + dp[i + 1][j - 1][0] how[i][j][k] = 0 # Representing choosing to take the line # Reconstruct the solution i, j, k = 0, lines_left, 6 taken_lines = [] while i < n: if how[i][j][k] == 0: # Chose to take the line taken_lines.append(n - i) i += 1 j -= 1 k = 0 else: # Chose not to take the line i += 1 k += 1 return dp[0][lines_left][6]
Below is one acceptable C translation. In this version we use variableâ€length arrays (a C99 feature) to create the threeâ€dimensional dp and how tables. (If your compiler does not support VLAs you will need to allocate the arrays dynamically.) Note that the reconstruction code is included as a comment, since the original function returns only the computed dp value. --------------------------------------------------- #include <stdio.h> float solve_dp(float *arr, int size, int lines_left) { int n = size; const int MAXK = 10; float INF = 1e9f; // Declare dp and how arrays with dimensions [n+1][lines_left+1][10] float dp[n+1][lines_left+1][MAXK]; int how[n+1][lines_left+1][MAXK]; int i, j, k; // Initialization: for all i, j, k set dp = INF except base case for (i = n; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { if (i == n && j == 0) dp[i][j][k] = 0; else dp[i][j][k] = INF; how[i][j][k] = -1; } } } // Fill the dp table in reverse order so that dp[i+1] is already computed. for (i = n - 1; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { // Option 1: Do not take the line (if possible). if (k < 9) { // Only safe to use k+1 when k<9. if (dp[i+1][j][k+1] < dp[i][j][k]) { dp[i][j][k] = dp[i+1][j][k+1]; how[i][j][k] = k + 1; // Mark decision as "not taking" (advance k). } } // Option 2: Take the line, if available (j > 0). if (j > 0) { // cost includes the value in arr[i] plus penalty: (k-8)^2. float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[i+1][j-1][0]; // Reset k to 0. if (candidate < dp[i][j][k]) { dp[i][j][k] = candidate; how[i][j][k] = 0; // Mark decision as "taking" the line. } } } } } // (Optional) Reconstruct the solution. This code is provided as a comment. /* int curr_i = 0, curr_j = lines_left, curr_k = 6; // In Python, taken_lines appended (n - curr_i). In C, you may store these in an array. while (curr_i < n) { if (how[curr_i][curr_j][curr_k] == 0) { // chose to take the line // For example, you could print or store (n - curr_i) printf("Take line at position: %d\n", n - curr_i); curr_i++; curr_j--; curr_k = 0; } else { // chose not to take the line curr_i++; curr_k++; } } */ return dp[0][lines_left][6]; } // Example usage: int main(void) { // For a simple test, define a graph (array of floats) and parameters: float graph[] = {1.0f, 2.5f, 3.0f, 4.2f, 5.1f}; int size = sizeof(graph) / sizeof(graph[0]); int lines_left = 2; float result = solve_dp(graph, size, lines_left); printf("Result: %f\n", result); return 0; } --------------------------------------------------- Explanation: 1. The dp table is defined as float dp[n+1][lines_left+1][10] (and similarly for the how table). We initialize every entry to INF (1e9f) except for the base case dp[n][0][*] = 0. 2. We fill the table in reverse order by iterating i from n-1 down to 0. For each state (i,j,k) we check two options: • Option 1: If not taking the line (provided k < 9 so that k+1 is in bounds), then dp[i][j][k] can be updated with dp[i+1][j][k+1]. • Option 2: If taking the line (i.e. j > 0) then compute cost = arr[i] + (k-8)² plus dp[i+1][j-1][0]. 3. Finally, the function returns dp[0][lines_left][6], which is the original problem’s answer. This solution should be equivalent in behavior to the original Python program.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <stdio.h> float solve_dp(float *arr, int size, int lines_left) { int n = size; const int MAXK = 10; float INF = 1e9f; // Declare dp and how arrays with dimensions [n+1][lines_left+1][10] float dp[n+1][lines_left+1][MAXK]; int how[n+1][lines_left+1][MAXK]; int i, j, k; // Initialization: for all i, j, k set dp = INF except base case for (i = n; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { if (i == n && j == 0) dp[i][j][k] = 0; else dp[i][j][k] = INF; how[i][j][k] = -1; } } } // Fill the dp table in reverse order so that dp[i+1] is already computed. for (i = n - 1; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { // Option 1: Do not take the line (if possible). if (k < 9) { // Only safe to use k+1 when k<9. if (dp[i+1][j][k+1] < dp[i][j][k]) { dp[i][j][k] = dp[i+1][j][k+1]; how[i][j][k] = k + 1; // Mark decision as "not taking" (advance k). } } // Option 2: Take the line, if available (j > 0). if (j > 0) { // cost includes the value in arr[i] plus penalty: (k-8)^2. float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[i+1][j-1][0]; // Reset k to 0. if (candidate < dp[i][j][k]) { dp[i][j][k] = candidate; how[i][j][k] = 0; // Mark decision as "taking" the line. } } } } } // (Optional) Reconstruct the solution. This code is provided as a comment. /* int curr_i = 0, curr_j = lines_left, curr_k = 6; // In Python, taken_lines appended (n - curr_i). In C, you may store these in an array. while (curr_i < n) { if (how[curr_i][curr_j][curr_k] == 0) { // chose to take the line // For example, you could print or store (n - curr_i) printf("Take line at position: %d\n", n - curr_i); curr_i++; curr_j--; curr_k = 0; } else { // chose not to take the line curr_i++; curr_k++; } } */ return dp[0][lines_left][6]; } |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <stdio.h> float solve_dp(float *arr, int size, int lines_left) { int n = size; const int MAXK = 10; float INF = 1e9f; // Declare dp and how arrays with dimensions [n+1][lines_left+1][10] float dp[n+1][lines_left+1][MAXK]; int how[n+1][lines_left+1][MAXK]; int i, j, k; // Initialization: for all i, j, k set dp = INF except base case for (i = n; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { if (i == n && j == 0) dp[i][j][k] = 0; else dp[i][j][k] = INF; how[i][j][k] = -1; } } } // Fill the dp table in reverse order so that dp[i+1] is already computed. for (i = n - 1; i >= 0; i--) { for (j = 0; j <= lines_left; j++) { for (k = 0; k < MAXK; k++) { // Option 1: Do not take the line (if possible). if (k < 9) { // Only safe to use k+1 when k<9. if (dp[i+1][j][k+1] < dp[i][j][k]) { dp[i][j][k] = dp[i+1][j][k+1]; how[i][j][k] = k + 1; // Mark decision as "not taking" (advance k). } } // Option 2: Take the line, if available (j > 0). if (j > 0) { // cost includes the value in arr[i] plus penalty: (k-8)^2. float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[i+1][j-1][0]; // Reset k to 0. if (candidate < dp[i][j][k]) { dp[i][j][k] = candidate; how[i][j][k] = 0; // Mark decision as "taking" the line. } } } } } // (Optional) Reconstruct the solution. This code is provided as a comment. /* int curr_i = 0, curr_j = lines_left, curr_k = 6; // In Python, taken_lines appended (n - curr_i). In C, you may store these in an array. while (curr_i < n) { if (how[curr_i][curr_j][curr_k] == 0) { // chose to take the line // For example, you could print or store (n - curr_i) printf("Take line at position: %d\n", n - curr_i); curr_i++; curr_j--; curr_k = 0; } else { // chose not to take the line curr_i++; curr_k++; } } */ return dp[0][lines_left][6]; } #include<stdio.h> #include<stdlib.h> int main() { float arr[] = {71, 89, 34, 63, 19, 94, 54, 61, 88, 20, 66, 46, 26, 87, 55, 81, 6, 2, 72, 75, 98, 78, 24, 95, 73, 7, 56, 48, 14, 99, 64, 51, 69, 77, 28, 47, 8, 22, 49, 3, 62, 32, 10, 82, 35, 18, 85, 60, 83, 23, 5, 40, 41, 68, 53, 52, 44, 45, 65, 84, 93, 25, 13, 1, 31, 11, 12, 97, 38, 0, 43, 90, 36, 70, 33, 17, 21, 30, 16, 15, 74, 67, 58, 37, 39, 96, 79, 29, 27, 92, 86, 9, 80, 42, 57, 91, 59, 4, 76, 50}; int answer = solve_dp(arr, 100, 100); int expected = 11290; if (answer != expected) { printf("Wrong answer; got %d instead of %d.\n", answer, expected); exit(1); } printf("All tests passed\n"); } |
All tests passed
Testing if the previous output contains the string All tests passed: True
Here's a python program. Please rewrite it in c with the type signature float solve_dp(float* arr, int size, int lines_left) def solve_dp(graph, lines_left): n = len(graph) dp = [[[1e9 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] # Initialize how as -1 indicating no decision made how = [[[-1 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] for i in range(n, -1, -1): for j in range(lines_left + 1): for k in range(10): if i == n and j == 0: dp[i][j][k] = 0 else: # Option 1: don't take the line if i < n and k < 9: if dp[i + 1][j][k + 1] < dp[i][j][k]: dp[i][j][k] = dp[i + 1][j][k + 1] how[i][j][k] = k + 1 # Representing choosing not to take the line # Option 2: take the line if i < n and j > 0: cost = graph[i] + (k - 8)**2 if cost + dp[i + 1][j - 1][0] < dp[i][j][k]: dp[i][j][k] = cost + dp[i + 1][j - 1][0] how[i][j][k] = 0 # Representing choosing to take the line # Reconstruct the solution i, j, k = 0, lines_left, 6 taken_lines = [] while i < n: if how[i][j][k] == 0: # Chose to take the line taken_lines.append(n - i) i += 1 j -= 1 k = 0 else: # Chose not to take the line i += 1 k += 1 return dp[0][lines_left][6]
Here's a python program. Please rewrite it in c with the type signature float solve_dp(float* arr, int size, int lines_left) def solve_dp(graph, lines_left): n = len(graph) dp = [[[1e9 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] # Initialize how as -1 indicating no decision made how = [[[-1 for _ in range(10)] for _ in range(lines_left + 1)] for _ in range(n + 1)] for i in range(n, -1, -1): for j in range(lines_left + 1): for k in range(10): if i == n and j == 0: dp[i][j][k] = 0 else: # Option 1: don't take the line if i < n and k < 9: if dp[i + 1][j][k + 1] < dp[i][j][k]: dp[i][j][k] = dp[i + 1][j][k + 1] how[i][j][k] = k + 1 # Representing choosing not to take the line # Option 2: take the line if i < n and j > 0: cost = graph[i] + (k - 8)**2 if cost + dp[i + 1][j - 1][0] < dp[i][j][k]: dp[i][j][k] = cost + dp[i + 1][j - 1][0] how[i][j][k] = 0 # Representing choosing to take the line # Reconstruct the solution i, j, k = 0, lines_left, 6 taken_lines = [] while i < n: if how[i][j][k] == 0: # Chose to take the line taken_lines.append(n - i) i += 1 j -= 1 k = 0 else: # Chose not to take the line i += 1 k += 1 return dp[0][lines_left][6]
Below is one valid C translation. In this version we allocate two 1â€D arrays (dp and how) that simulate threeâ€dimensional arrays with dimensions [size+1][lines_left+1][10]. We use a macro IDX(i,j,k) to compute the index into the flattened array. (Note that the “how†array is computed here for completeness even though it is only used for solution reconstruction in your Python code.) Below is the complete C code for the solve_dp function: ----------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #define INF 1e9 // Macro to compute the index for the dp and how arrays. // The arrays are dimensioned as [size+1][lines_left+1][10] // idx(i, j, k) = ((i * (lines_left+1) + j) * 10 + k) #define IDX(i, j, k, lines_left) ((((i) * ((lines_left)+1) + (j)) * 10) + (k)) float solve_dp(float* arr, int size, int lines_left) { int total = (size + 1) * (lines_left + 1) * 10; float *dp = malloc(total * sizeof(float)); int *how = malloc(total * sizeof(int)); if (!dp || !how) { // Memory allocation error fprintf(stderr, "Memory allocation error.\n"); exit(1); } // Initialize dp with INF and how with -1 for (int i = 0; i < total; i++) { dp[i] = INF; how[i] = -1; } // Fill dp and how arrays in reverse order. // i: from size down to 0, // j: from 0 to lines_left, // k: from 0 to 9. for (int i = size; i >= 0; i--) { for (int j = 0; j <= lines_left; j++) { for (int k = 0; k < 10; k++) { // Base case: When at the end (i == size) and no lines remain. if (i == size && j == 0) { dp[IDX(i, j, k, lines_left)] = 0.0f; } else { // Option 1: Do not take the current line // Only available if there is a next row and k < 9 if (i < size && k < 9) { float candidate = dp[IDX(i+1, j, k+1, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = k+1; // mark decision } } // Option 2: Take the line (if remaining lines available) if (i < size && j > 0) { float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[IDX(i+1, j-1, 0, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = 0; // mark decision } } } } } } // (Optional) Reconstruct the solution path using the "how" array. // The Python code collects an array "taken_lines". // Here we demonstrate the reconstruction for clarity. int i = 0, j = lines_left, k = 6; // For demonstration, we print the "taken line" positions. // Uncomment the following lines if you wish to see the decision path. /* printf("Taken lines (positions from the end of arr):\n"); while (i < size) { int decision = how[IDX(i, j, k, lines_left)]; if (decision == 0) { // Chose to take the line printf("%d ", size - i); i++; j--; k = 0; } else { // Chose NOT to take the line i++; k++; } } printf("\n"); */ float result = dp[IDX(0, lines_left, 6, lines_left)]; free(dp); free(how); return result; } // Example main() function to test solve_dp /* int main(void) { float graph[] = {1.0f, 2.0f, 3.0f, 4.0f}; int size = sizeof(graph) / sizeof(graph[0]); int lines_left = 2; float result = solve_dp(graph, size, lines_left); printf("Result: %f\n", result); return 0; } */ ----------------------------------------------------------- Explanation: 1. We allocate arrays dp and how to simulate a 3D array with dimensions [size+1][lines_left+1][10]. The macro IDX(i, j, k, lines_left) converts 3D indices into a 1D index. 2. We initialize dp with INF (1e9) and how with –1. 3. The nested loops fill in the dp array in reverse order (starting with i = size). 4. Two options are considered: • Option 1 (don’t take the line) is valid if i < size and k < 9. • Option 2 (take the line) is valid if i < size and j > 0. 5. Finally, the function returns dp[0][lines_left][6]. You can uncomment the main() function to compile and test this code.
I extracted the following code from that output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <stdio.h> #include <stdlib.h> #define INF 1e9 // Macro to compute the index for the dp and how arrays. // The arrays are dimensioned as [size+1][lines_left+1][10] // IDX(i, j, k, lines_left) = ((i * (lines_left+1) + j) * 10 + k) #define IDX(i, j, k, lines_left) ((((i) * ((lines_left)+1) + (j)) * 10) + (k)) float solve_dp(float* arr, int size, int lines_left) { int total = (size + 1) * (lines_left + 1) * 10; float *dp = malloc(total * sizeof(float)); int *how = malloc(total * sizeof(int)); if (!dp || !how) { // Memory allocation error fprintf(stderr, "Memory allocation error.\n"); exit(1); } // Initialize dp with INF and how with -1 for (int i = 0; i < total; i++) { dp[i] = INF; how[i] = -1; } // Fill dp and how arrays in reverse order. // i: from size down to 0, // j: from 0 to lines_left, // k: from 0 to 9. for (int i = size; i >= 0; i--) { for (int j = 0; j <= lines_left; j++) { for (int k = 0; k < 10; k++) { // Base case: When at the end (i == size) and no lines remain. if (i == size && j == 0) { dp[IDX(i, j, k, lines_left)] = 0.0f; } else { // Option 1: Do not take the current line // Only available if there is a next row and k < 9 if (i < size && k < 9) { float candidate = dp[IDX(i+1, j, k+1, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = k+1; // mark decision } } // Option 2: Take the line (if remaining lines available) if (i < size && j > 0) { float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[IDX(i+1, j-1, 0, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = 0; // mark decision } } } } } } // (Optional) Reconstruct the solution path using the "how" array. // The Python code collects an array "taken_lines". // Here we demonstrate the reconstruction for clarity. int i = 0, j = lines_left, k = 6; /* Uncomment the following lines if you wish to see the decision path. printf("Taken lines (positions from the end of arr):\n"); while (i < size) { int decision = how[IDX(i, j, k, lines_left)]; if (decision == 0) { // Chose to take the line printf("%d ", size - i); i++; j--; k = 0; } else { // Chose NOT to take the line i++; k++; } } printf("\n"); */ float result = dp[IDX(0, lines_left, 6, lines_left)]; free(dp); free(how); return result; } |
Running the following program:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <stdio.h> #include <stdlib.h> #define INF 1e9 // Macro to compute the index for the dp and how arrays. // The arrays are dimensioned as [size+1][lines_left+1][10] // IDX(i, j, k, lines_left) = ((i * (lines_left+1) + j) * 10 + k) #define IDX(i, j, k, lines_left) ((((i) * ((lines_left)+1) + (j)) * 10) + (k)) float solve_dp(float* arr, int size, int lines_left) { int total = (size + 1) * (lines_left + 1) * 10; float *dp = malloc(total * sizeof(float)); int *how = malloc(total * sizeof(int)); if (!dp || !how) { // Memory allocation error fprintf(stderr, "Memory allocation error.\n"); exit(1); } // Initialize dp with INF and how with -1 for (int i = 0; i < total; i++) { dp[i] = INF; how[i] = -1; } // Fill dp and how arrays in reverse order. // i: from size down to 0, // j: from 0 to lines_left, // k: from 0 to 9. for (int i = size; i >= 0; i--) { for (int j = 0; j <= lines_left; j++) { for (int k = 0; k < 10; k++) { // Base case: When at the end (i == size) and no lines remain. if (i == size && j == 0) { dp[IDX(i, j, k, lines_left)] = 0.0f; } else { // Option 1: Do not take the current line // Only available if there is a next row and k < 9 if (i < size && k < 9) { float candidate = dp[IDX(i+1, j, k+1, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = k+1; // mark decision } } // Option 2: Take the line (if remaining lines available) if (i < size && j > 0) { float cost = arr[i] + (float)((k - 8) * (k - 8)); float candidate = cost + dp[IDX(i+1, j-1, 0, lines_left)]; if (candidate < dp[IDX(i, j, k, lines_left)]) { dp[IDX(i, j, k, lines_left)] = candidate; how[IDX(i, j, k, lines_left)] = 0; // mark decision } } } } } } // (Optional) Reconstruct the solution path using the "how" array. // The Python code collects an array "taken_lines". // Here we demonstrate the reconstruction for clarity. int i = 0, j = lines_left, k = 6; /* Uncomment the following lines if you wish to see the decision path. printf("Taken lines (positions from the end of arr):\n"); while (i < size) { int decision = how[IDX(i, j, k, lines_left)]; if (decision == 0) { // Chose to take the line printf("%d ", size - i); i++; j--; k = 0; } else { // Chose NOT to take the line i++; k++; } } printf("\n"); */ float result = dp[IDX(0, lines_left, 6, lines_left)]; free(dp); free(how); return result; } #include<stdio.h> #include<stdlib.h> int main() { float arr[] = {71, 89, 34, 63, 19, 94, 54, 61, 88, 20, 66, 46, 26, 87, 55, 81, 6, 2, 72, 75, 98, 78, 24, 95, 73, 7, 56, 48, 14, 99, 64, 51, 69, 77, 28, 47, 8, 22, 49, 3, 62, 32, 10, 82, 35, 18, 85, 60, 83, 23, 5, 40, 41, 68, 53, 52, 44, 45, 65, 84, 93, 25, 13, 1, 31, 11, 12, 97, 38, 0, 43, 90, 36, 70, 33, 17, 21, 30, 16, 15, 74, 67, 58, 37, 39, 96, 79, 29, 27, 92, 86, 9, 80, 42, 57, 91, 59, 4, 76, 50}; int answer = solve_dp(arr, 100, 100); int expected = 11290; if (answer != expected) { printf("Wrong answer; got %d instead of %d.\n", answer, expected); exit(1); } printf("All tests passed\n"); } |
All tests passed
Testing if the previous output contains the string All tests passed: True