C语言 | Leetcode C语言题解之第375题猜数字大小II

题目：

题解：

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>#define MMAX(a, b)        ((a) > (b)? (a) : (b))
#define MMIN(a, b)        ((a) < (b)? (a) : (b))#define MAX_LEN     1000int dp[MAX_LEN][MAX_LEN];//【算法思路】分组DP。
int getMoneyAmount(int n){if(n == 1) {return 0;}for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {dp[i][j] = 0;}}for(int gap = 0; gap < n; gap++) {for(int i = 0; i + gap < n; i++) {int j = i + gap;if(gap == 0) {dp[i][j] = 0;continue;}int min = MMIN(i + 1 + dp[i + 1][j], j + 1 + dp[i][j - 1]);for(int k = i + 1; k < j; k++) {min = MMIN(min, k + 1 + MMAX(dp[i][k - 1], dp[k + 1][j]));}dp[i][j] = min;}}
/*for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {printf("dp[%d, %d] = %d     ", i, j, dp[i][j]);}printf("\n");}
*/return dp[0][n - 1];
}