动态规划算法的思想及实现

includecmath 发布于2019-08-20 14:01 / 2128人阅读

摘要：介绍动态规划简称是算法设计思想当中最难也是最有趣的部分了，动态规划适用于有重叠子问题和最优子结构性质的问题，是一种在数学计算机科学和经济学中经常使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

介绍

动态规划(简称DP)是算法设计思想当中最难也是最有趣的部分了，动态规划适用于有重叠子问题和最优子结构性质的问题，是一种在数学、计算机科学和经济学中经常使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。使用动态规划方法解题有较高的时间效率，关键在于它减少了很多不必要的计算和重复计算的部分

它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划

最优子结构性: 既所拆分的子问题的解是最优解。

子问题重叠性质: 既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率

举个栗子

首先先引一道动态规划的经典问题最长不下降子序列

它的定义是: 设有由n个不相同的整数组成的数列b[n],若有下标$i_1

例如

13,7,9,16,38,24,37,18,44,19,21,22,63,15

那么就有13<16<38<44<63长度为5的不下降子序列。
但是经过观察实际上还有7<9<16<18<19<21<22<63长度为8的不下降子序列，那么是否还有更长的不下降子序列呢？请找出最长的不下降子序列

输入格式

第一行为n，表示n个数(n<=100000),第二行为n个数的数值(数字之间用空格隔开且最后一个数字末尾不能留有空格)

输出格式

一个整数，表示最长不下降子序列的长度。

输入例子

1 3 1 2

输出例子

思路

假如要求得某一段的最优，就要想更小段的最优怎么求，再看看由最小段的最优能否扩大推广到最大段的最优;

假设这么一个表:

第三行表示该序列元素的所能连接的最长不下降子序列的长度，因为本身长度为1，所以初始值都为1

第四行表示链接于哪个序列元素形成最长不下降子序列

先从倒数第二项63算起，在它的后面仅有一项，因此仅作一次比较，因为63>15，所以从63出发，不作任何链接，长度还是为1。

再看倒数第三项22，在它的后面有2项，因此必须要在这2项当中找出比22大，长度又是最长的数值作为链接，由于只有22<63,所以修改22的长度为2，即自身长度加上所链接数值的长度，并修改链接位置为13，也就是63的下标。

再看倒数第四项21，在它的后面有3项，因此必须要在这3项当中找出比21大，长度又是最长的数值作为链接(注意:是长度)，很容易看出，数值22满足该条件，因此，修改21的长度为3，并修改链接位置为12，即22的序列下标。

依次类推，最后结果如下表:

最终状态的转移方程式为: $f(i) = max {f(j)} +1 (b_j

代码

process.stdin.setEncoding("utf8");

var arr = [];
var bool = 0;
var n = 0;
var longest = 1;
var a = [];
var dp = [];

process.stdin.on("readable", function() {
  var chunk = process.stdin.read();
  if (chunk !== null) {
      arr.push(chunk.trim())
  }

  if(bool>=2){
      n = arr[0];
      process.stdin.emit("end")
  }

  bool++

});


process.stdin.on("end", function() {

    a = arr.slice(1).join(" ").split(" ").map(function(index, elem) {
        return parseInt(index);
    })

    for(let i = 0;ia[j]){
                dp[i] = Math.max(dp[j]+1,dp[i])
            }
            longest = Math.max(dp[i],longest)
        }

    }

    console.log("最长长度为:"+longest);


      process.stdout.write("end");
});

私有云海外云主机最优合并问题的算法思想最短路径算法思想动态规划动态html的实现

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

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

基本算法思想：递归+分治+动态规划+贪心+回溯+分支限界

摘要：代码实现见下面评论对应代码动态规划基本思想和分治法基本思想有共同的地方，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因此把已经计算好的问题记录在表格中，后续如果需要查询一下，可以避免重复计算，这是动态规划的基本思想。作者：心叶时间：2018-05-01 19:28 本文对应github地址：https://github.com/yelloxing/... 以上实现...

EscapedDog 2019-08-26 11:52 评论0 收藏0
前端跳槽面试算法——动态规划

摘要：我记得大三参加腾讯的校招面试时只准备了几种常见的排序算法就足以应对了，然而今年包括今日头条在内的多家大厂的前端笔试题目中都出现了贪心算法动态规划分治算法等进阶性的算法题目。本篇博客参考今日头条银国徽老师的《js版数据结构与算法》Part1改编自《漫画算法》原作者：程序员小灰前言众所周知，与后台开发人员相比，算法是我们前端开发人员的一个弱项。而近两年随着互联网行业竞争愈发激烈，市场上对前端岗位...

mushang 2019-05-21 19:07 评论0 收藏0
从斐波那契数列看递归和动态规划

摘要：大名鼎鼎的斐波那契数列，，，，，，，，使用数学归纳法可以看出其规律为。对于斐波那契数列的求解，有自顶向下的记忆化搜索递归和自下向上的迭代法，他们都使用了动态规划的思想。大名鼎鼎的斐波那契数列：0，1，1，2，3，5，8，13，21...使用数学归纳法可以看出其规律为：f(n) = f(n-1) + f(n-2)。递归下面首先直接使用递归（JavaScript实现）来求解第 n ...

charles_paul 2019-08-22 18:30 评论0 收藏0
动态规划入门（以爬楼梯为例）

摘要：动态规划算法通常基于一个递推公式及一个或多个初始状态。动态规划有三个核心元素最优子结构边界状态转移方程我们来看一到题目题目有一座高度是级台阶的楼梯，从下往上走，每跨一步只能向上级或者级台阶。概念动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常基于一个递推公式及一个或多个初始状态...

cyixlq 2019-08-23 10:52 评论0 收藏0