动态规划-Minimum Cost to Merge Stones
2024-09-06 04:03:58
2019-07-07 15:48:46
问题描述:
问题求解:
最初看到这个问题的时候第一反应就是这个题目和打破气球的题目很类似。
但是我尝试了使用dp将问题直接转为直接合并到一个堆问题复杂度迅速提高并且并没有ac,这里的思想是和打爆气球一致的,就是找最后合并的部分。
Discuss里给出了可以过的代码,思路其实和打破气球是不一致的。
这里的想法是先把i-j的数组分成K堆,然后就可以将这K堆直接merge到1堆中。因此就还有一个维度就是堆数。
总的来说,dp的题目还是非常的灵活,需要多多练习。
dp[i][j][k] := min cost to merge subarray i ~ j into k piles
Init: dp[i][j][k] = 0 if i==j and k == 1 else inf
ans: dp[0][n-1][1]
transition:
1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j
2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])
public int mergeStones(int[] stones, int K) {
int n = stones.length;
int[][][] dp = new int[n][n][K + 1];
int[] sum = new int[n];
sum[0] = stones[0];
for (int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + stones[i];
}
init(dp, n, K);
for (int i = 0; i < n; i++) dp[i][i][1] = 0;
for (int l = 2; l <= n; l++) {
for (int i = 0; i <= n - l; i++) {
int j = i + l - 1;
for (int k = 2; k <= K; k++) {
for (int m = i; m < j; m++) {
dp[i][j][k] = Math.min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j] [k - 1]);
}
}
dp[i][j][1] = Math.min(dp[i][j][1], dp[i][j][K] + sum[j] - sum[i] + stones[i]);
}
}
return dp[0][n - 1][1] == (int)1e9 ? -1 : dp[0][n - 1][1];
} private void init(int[][][] dp, int n, int K) {
int inf = (int)1e9;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k <= K; k++)
dp[i][j][k] = inf;
}
}
}
最新文章
- 【总结】使用WebBrowser遇到的陷阱
- xcode8 info.plist文件中的各种权限。
- tomcat域名问题
- swift学习笔记之-析构过程
- js延迟加载,提升网页加载速度
- Asp.net Mvc对比Php的4大误解
- ASP.NET Core 源码学习之 Logging[3]:Logger
- CentOS中安装配置Nginx
- libpqxx接口的在linux下的使用,解决psql:connections on Unix domain socket ";/tmp/.s.PGSQL.5432";错误
- [ERROR] - Error reading string. Unexpected token: StartObject. Path &#39;formData&#39;, line 1, position 13.
- 同步手绘板——android端取色
- 关于idea通过smalidea无源调试apk
- [linux] C语言Linux系统编程-捕获进程信号
- PhpStorm 自定义快捷键
- kubeadm搭建kubernetes集群之二:创建master节点
- Nginx源码完全注释(2)ngx_array.h / ngx_array.c
- python内建datetime模块
- libvirt cpu mode
- 2、SpringBoot------数据转换
- java之struts框架入门教程