DP 区间 - wenzhoullq/leetcode GitHub Wiki
枚举分组
int len = nums.length;
double[][] dp = new double[len+1][k+1];
for(int i = 1 ; i <= len ; i++){//初始化
dp[i][1] = sum[i]/i;
}
for(int i = 2;i <= len; i++){//枚举终点
for(int j = 2; j <= k ;j++){//枚举分组
for(int l = 0; l <i ;l++){//枚举起点
dp[i][j] = Math.max(dp[i][j],dp[l][j-1]+);
}
}
}
return dp[len][k];
题目
枚举区间(长度)
int len = arr.length;
int[] dp = new int[len+1];
for(int i = 1 ; i <= len ;i++){
for(int j = i ; j >=Math.max(1,i-k+1); j--){//k是长度
//处理
dp[i] = Math.max(dp[i],dp[j-1]+___);
}
}
return dp[len];
题目
枚举区间(分割点）
//根据题意预处理
int[][] dp = new int[len][d+1];//注意len和d+1
for(int i = 0; i < len; i++) {
dp[i][1] = ;//初始化第一个区间
}
for(int i = 0; i < len ; i++){//从0 开始
for(int j = 2; j<= d; j++){//区间为1的已经处理过了,一直处理到j=d
dp[i][j] = INF;
for(int k = i ;k >=1 ;k--){//终点是k >= 1
dp[i][j] = Math.min(dp[i][j],dp[k-1][j-1]+max);//注意k的处理
}
}
}
return dp[len-1][d];//注意下标
题目
闭区间
像合并类的，采用的是闭区间，代价是前缀和
for(int i = 2 ; i <= len; i++) //枚举区间长度
for( int j = 0; j + i -1< len ;j++) //枚举起点
int k = j + i -1;
for( int l = k; l <k ;l++) //枚举分割点，值得注意的是，因为分割点在l和l+1,因此 l < k
201. 石子合并2 破环成链，且最大值在长度为[0,len-1]上取
P1880 [NOI1995] 石子合并 破环成链
开区间
因为取后有影响，注意取得起点
for(int i = 3 ; i<=len ;i++ )//枚举区间长度,注意取得初始长度
for(int j = 0;j + i -1< len;j++) // 枚举区间起点
int k = j+ i -1;
for(int l = j + 1;l < k ; l++)// 枚举区间中的点,注意被取的起点和终点
题目
- 区间博弈
dp代表（i,j）内先手，用num[i]-dp代表自己手里的数目