摘要:动态规划练习题汇总描述有堆石子排成一排,每堆石子有一定的数量。现要将堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过次合并后成为一堆。
动态规划练习题汇总
描述
有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
输入
序列n,序列值表示第i堆石子的数量,0<=i
输出总代价的最小值
1 思路
最先合并的石子堆在后期中可能被多次合并,因此最先合并的石子堆数量越小越好
2 拆分子问题
每次进行合并,需要从当前的石子堆中选取两个相邻的石子数量和最少的作为被合并的堆
3 计算 4 代码 recursive DP 5 时间复杂度
令第i次合并后的总代价为C(i),C(0)=0,则C(i+1)=C(i)+min{序列[k]+序列[k+1]},其中 0<=i
bottom-up DPconst stoneArray = [4, 2, 3, 9, 6, 8, 1, 7];
class CalStone {
constructor(options) {
this.stoneArray = Array.isArray(options) ? options : [];
}
getStoreBottomUp() {
let i = 0;
const len = this.stoneArray.length;
while (++i < len) {
let min = { sum: 99999999999, index: [-1, -1] };
for (let i = 0; i < this.stoneArray.length - 1;i++){
const sum = this.stoneArray[i] + this.stoneArray[i + 1];
min = sum < min.sum ? { sum: sum, index: [i, i + 1] } : min;
}
this.stoneArray = [].concat(this.stoneArray.slice(0, min.index[0]), min.sum, this.stoneArray.slice(min.index[1]+1));
}
console.log(`总代价为 ${this.stoneArray[0]}`);
}
}
new CalStone(stoneArray).getStoreBottomUp();
const stoneArray = [4, 2, 3, 9, 6, 8, 1, 7];
class CalStone {
constructor(options) {
this.stoneArray = Array.isArray(options) ? options : [];
}
getStoneRecursive(arr = this.stoneArray) {
if (arr.length === 1) {
console.log(`总代价为 ${arr[0]}`);
return arr;
} else {
let min = { sum: 99999999999, index: [-1, -1] };
for (let i = 0; i < arr.length - 1; i++) {
const sum = arr[i] + arr[i + 1];
min = sum < min.sum ? { sum: sum, index: [i, i + 1] } : min;
}
const newStoneArr = [].concat(arr.slice(0, min.index[0]), min.sum, arr.slice(min.index[1] + 1));
return this.getStoneRecursive(newStoneArr);
}
}
}
new CalStone(stoneArray).getStoneRecursive();
需要进行n-1次合并,第i次合并需要进行n-i次比较,故时间复杂度为O(n2)
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/110004.html
摘要:动态规划练习题汇总题目描述传说中的九头龙是一种特别贪吃的动物。如上图中的输出输出一个整数,表示在满足大头的要求的前提下,九头龙的难受值的最小值。 动态规划练习题汇总 题目描述传说中的九头龙是一种特别贪吃的动物。虽然名字叫九头龙,但这只是说它出生的时候有九个头,而在成长的过程中,它有时会长出很多的新头,头的总数会远大于九,当然也会有旧头因衰老而自己脱落。有一天,有M个脑袋的九头龙看到一棵...
摘要:动态规划练习题总题目描述设一个个节点的二叉树的中序遍历为,其中数字为节点编号。若某个子树为空,规定其加分为,叶子的加分就是叶节点本身的分数。试求一棵符合中序遍历为且加分最高的二叉树。 动态规划练习题-总 题目描述设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及...
马上就要开始啦这次共组织15个组队学习 涵盖了AI领域从理论知识到动手实践的内容 按照下面给出的最完备学习路线分类 难度系数分为低、中、高三档 可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...
阅读 790·2021-10-09 09:44
阅读 693·2019-08-30 13:55
阅读 3156·2019-08-29 15:07
阅读 3220·2019-08-29 13:09
阅读 2413·2019-08-29 11:10
阅读 1292·2019-08-26 14:05
阅读 3594·2019-08-26 13:57
阅读 2208·2019-08-23 16:42