动态规划练习题-石子合并

ziwenxie 发布于2019-08-26 14:05 / 1265人阅读

摘要：动态规划练习题汇总描述有堆石子排成一排，每堆石子有一定的数量。现要将堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过次合并后成为一堆。

动态规划练习题汇总

描述
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
序列n，序列值表示第i堆石子的数量，0<=i输出
输出总代价的最小值

1 思路
最先合并的石子堆在后期中可能被多次合并，因此最先合并的石子堆数量越小越好

2 拆分子问题
每次进行合并，需要从当前的石子堆中选取两个相邻的石子数量和最少的作为被合并的堆

3 计算
令第i次合并后的总代价为C(i)，C(0)=0，则C(i+1)=C(i)+min{序列[k]+序列[k+1]}，其中 0<=i

4 代码
bottom-up DP

const 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();

recursive DP

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();

5 时间复杂度
需要进行n-1次合并，第i次合并需要进行n-i次比较，故时间复杂度为O(n2)

GPU云服务器云服务器动态规划动态规划python java动态规划代码 java零钱动态规划

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/110004.html

动态规划练习题-总

摘要：最近学习了动态规划的四节网课，想上手练习，故写文章留作纪念，文章的主要内容是解题思路，代码用写练习题分为四种，线性动规拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等，区域动规石子合并，加分二叉树，统计单词个数，炮兵布阵等，树形动规贪吃的九头最近学习了动态规划的四节网课，想上手练习，故写文章留作纪念，文章的主要内容是解题思路，代码用JS写练习题分为四种：1，线性动规：拦截导弹，合唱队...

yacheng 2019-08-26 14:01 评论0 收藏0
动态规划练习题-贪吃的九头龙

摘要：动态规划练习题汇总题目描述传说中的九头龙是一种特别贪吃的动物。如上图中的输出输出一个整数，表示在满足大头的要求的前提下，九头龙的难受值的最小值。动态规划练习题汇总题目描述传说中的九头龙是一种特别贪吃的动物。虽然名字叫九头龙，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。有一天，有M个脑袋的九头龙看到一棵...

MockingBird 2019-08-26 11:00 评论0 收藏0
动态规划练习题-加分二叉树

摘要：动态规划练习题总题目描述设一个个节点的二叉树的中序遍历为，其中数字为节点编号。若某个子树为空，规定其加分为，叶子的加分就是叶节点本身的分数。试求一棵符合中序遍历为且加分最高的二叉树。动态规划练习题-总题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及...

Miracle 2019-08-26 14:06 评论0 收藏0
第7期 Datawhale 组队学习计划

马上就要开始啦这次共组织15个组队学习涵盖了AI领域从理论知识到动手实践的内容按照下面给出的最完备学习路线分类难度系数分为低、中、高三档可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 评论0 收藏0