diff options
author | Jack Sangdahl <[email protected]> | 2025-09-28 20:28:49 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-28 20:28:49 -0600 |
commit | c940fddbdbf26edb345954e2b155f87ad3aae7ae (patch) | |
tree | 948a02c8d247e090f3e9e99c26d63298acee7ecf /min_score_polygon.c | |
parent | 60f3439c8377ef8b99b5055b471840d53ab200a0 (diff) | |
download | leetcode-c940fddbdbf26edb345954e2b155f87ad3aae7ae.tar.gz leetcode-c940fddbdbf26edb345954e2b155f87ad3aae7ae.zip |
1039. minimum score triangulation of polygon
Diffstat (limited to 'min_score_polygon.c')
-rw-r--r-- | min_score_polygon.c | 47 |
1 files changed, 16 insertions, 31 deletions
diff --git a/min_score_polygon.c b/min_score_polygon.c index de648d9..9695365 100644 --- a/min_score_polygon.c +++ b/min_score_polygon.c @@ -1,8 +1,5 @@ // 1039. Minimum Score Triangulation of Polygon -#include <limits.h> -#include <math.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given a convex n-sided polygon where each vertex has an integer value. you @@ -15,36 +12,24 @@ * triangulation of the polygon */ -int minScoreTriangulation(int *values, int values_size) { - int n = values_size, **dp = malloc(n * sizeof(int *)); - for (int i = 0; i < n; i++) { - dp[i] = malloc(n * sizeof(int)); - dp[i][i] = 0; - if (i + 1 < n) - dp[i][i + 1] = 0; - for (int j = i + 2; j < n; j++) - dp[i][j] = INT_MAX / 3; - } - for (int len = 3; len <= n; len++) { - for (int i = 0; i < n; i++) { - int j = i + len - 1; - if (j >= n) - break; - for (int k = i + 1; k < j; k++) - dp[i][j] = fmin(dp[i][j], dp[i][k] + values[i] * values[k] * values[j] + - dp[k][j]); +int minScoreTriangulation(int *values, int valuesSize) { + int dp[50][50] = {0}; + for (int i = 2; i < valuesSize; i++) + for (int j = 0; j + i < valuesSize; j++) { + int k = j + i; + dp[j][k] = INT_MAX; + for (int l = j + 1; l < k; l++) { + int score = dp[j][l] + dp[l][k] + values[j] * values[k] * values[l]; + if (score < dp[j][k]) + dp[j][k] = score; + } } - } - int ans = dp[0][n - 1]; - for (int i = 0; i < n; i++) - free(dp[i]); - free(dp); - return ans; + return dp[0][valuesSize - 1]; } int main() { int v1[] = {1, 2, 3}, v2[] = {3, 7, 4, 5}, v3[] = {1, 3, 1, 4, 1, 5}; - printf("%d\n", minScoreTriangulation(v1, 3)); // expect: 6 - printf("%d\n", minScoreTriangulation(v2, 4)); // expect: 144 - printf("%d\n", minScoreTriangulation(v3, 6)); // expect: 13 + printf("%d\n", minScoreTriangulation(v1, ARRAY_SIZE(v1))); // expect: 6 + printf("%d\n", minScoreTriangulation(v2, ARRAY_SIZE(v2))); // expect: 144 + printf("%d\n", minScoreTriangulation(v3, ARRAY_SIZE(v3))); // expect: 13 } |