当前位置：文档之家 › 动态规划题目

动态规划题目

  • 格式：docx
  • 大小：36.84 KB
  • 文档页数：2

动态规划题目

动态规划（Dynamic Programming）是一种常用的求解最优化问题的方法。它的核心思想是，将问题拆解成若干个子问题，并保存子问题的解，以便后续计算。通过利用子问题的解，逐步求得原问题的最优解。

一个典型的动态规划问题可以用一个简单的例子来说明。假设有一段长度为n的绳子，我们希望将它切割成若干段，使得乘积最大。例如，当n=8时，我们可以切割成长度为2、3和3的三段，此时乘积最大，为18。这个问题可以用动态规划来解决。

首先，我们定义一个数组dp，其中dp[i]表示长度为i的绳子的乘积最大值。显然，dp[0]=0，dp[1]=1，dp[2]=2，dp[3]=3。然后，我们需要考虑长度大于3的情况。对于长度为i的绳子，我们可以将其切割成两段，长度为j和i-j。那么，长度为i的绳子的乘积最大值可以表示为dp[j]*dp[i-j]。然后我们需要遍历所有可能的j的值，找出其中的最大值，作为dp[i]的值。具体的计算过程如下所示：

for i from 4 to n:

for j from 1 to i/2:

dp[i] = max(dp[i], dp[j]*dp[i-j])

最后，返回dp[n]即为所求的最大乘积。

动态规划的核心思想就是将问题拆解成子问题，并保存子问题的解，以便后续计算。在上述例子中，我们将长度为n的绳子切割成长度为j和i-j的两段，然后计算乘积最大值。这里的子问题是求解长度为j和长度为i-j的绳子的乘积最大值，因此可以利用dp数组保存子问题的解。

动态规划的时间复杂度和空间复杂度由问题的规模决定。在上述例子中，我们需要计算长度为n的绳子的最大乘积，需要进行两层循环遍历，因此时间复杂度为O(n^2)。空间复杂度则由dp数组决定，为O(n)。

动态规划是一种非常常见且有效的求解最优化问题的方法。通过将问题拆解成若干个子问题，并保存子问题的解，可以大大优化问题的求解过程。在实际应用中，我们可以通过改变子问题的定义和状态转移方程，来解决不同的问题。

合集下载

C++中的动态规划算法及常见题目汇总

C++中的动态规划算法及常见题目汇总

C++中的动态规划算法及常见题⽬汇总什么是动态规划在⾯试过程中如果是求⼀个问题的最优解（通常是最⼤值或者最⼩值），并且该问题能够分解成若⼲个⼦问题，并且⼦问题之间好友重叠的更⼩⼦问题，就可以考虑⽤动态规划来解决这个问题。

动态规划的分类 ⼤多数动态规划问题都可以被归类成两种类型：优化问题和组合问题

优化问题 优化问题就是我们常见的求⼀个问题最优解（最⼤值或者最⼩值）

组合问题 组合问题是希望你弄清楚做某事的数量或者某些事件发⽣的概率两种不同动态规划解决⽅案⾃上⽽下：即从顶端不断地分解问题，知道你看到的问题已经分解到最⼩并已得到解决，之后只⽤返回保存的答案即可

⾃下⽽上：你可以直接开始解决较⼩的⼦问题，从⽽获得最⼩的解决⽅案。在此过程中，你需要保证在解决问题之前先解决⼦问题。这种⽅法叫做表格填充法。

常见的动态规划例⼦

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11. 猜数字⼤⼩

　1. 裴波那契数列 裴波那契数列就是典型的组合问题，要求出做某事的数量或者概率

问题分析：对于题⽬中的青蛙爬楼梯问题，初试情况下是只有⼀级台阶时，只有⼀种跳法，只有两级台阶时，有两种跳法，当有n级台

阶时，设n级台阶的跳法总数是f(n),如果第⼀步跳⼀级台阶，则和剩下的n-1级台阶的跳法是⼀样的，如果第⼀级跳两级台阶，则和剩下

的n-2级台阶的跳法是⼀样的，因此最终n级台阶的跳法是f(n)=f(n-1)+f(n-2)，即其是可以被分解为更⼩的⼦问题的，下⾯我们以求解f(10)

为例来分析递归的过程

我们从这张图中不难发现，在这棵树中有很多节点都是重复的，⽽且重复节点会随着n的增⼤⽽急剧增⼤，因此我们采⽤⾃顶向下的⽅

式会有很低的效率，因此我们采⽤⾃下⽽上的⽅法，⾸先根据f(1)和f(2)计算出f(3),再根据f(2)和f(3计算出f(4),以此类推求出f(n)

实现的代码如下

1 int jumpFloor(int number) {

USACO上面的动态规划题目

USACO上面的动态规划题目

水题6 题目名称 修理牛棚 数字金字塔 集合 最长前缀 奶牛家谱

程序名 barn1 numtri subset prefix nocows

时间限制 1s 1s 1s 1s 1s

空间限制 16M 16M 16M 16M 16M

题目类型 传统 传统 传统 传统 传统

来源 USACO Section 1.3 USACO

Section 1.5 USACO

Section 2.2 USACO

Section 2.3 USACO

Section 2.3

题目名称 货币系统 总分 邮票 商店购物 家的范围

程序名 money inflate stamps shopping range

时间限制 1s 1s 1s 1s 1s

空间限制 16M 16M 16M 16M 16M

题目类型 传统 传统 传统 传统 传统

来源 USACO Section 2.3 USACO

Section 3.1 USACO

Section 3.1 USACO

Section 3.3 USACO

Section 3.3

题目名称 “破锣摇

滚”乐队 麦香牛块 逢低吸纳 巨大的牛棚 周游加拿

大

程序名 rockers nuggets buylow bigbrn tour

时间限制 1s 1s 1s 1s 1s

空间限制 16M 16M 16M 16M 16M

题目类型 传统 传统 传统 传统 传统

来源 USACO Section 3.4 USACO

Section 4.1 USACO

Section 4.3 USACO

Section 5.3 USACO

Section 5.4

题目名称 字符识别 邮政货车 矩形牛棚

提示：注意颜色深浅

与难度之间的联系 程序名 char vans rectbarn

时间限制 1s 1s 1s

空间限制 16M 16M 16M

题目类型 传统 传统 传统

来源 USACO Section 5.4 USACO

动态规划

动态规划

一．用动态规划方法手工求解以下问题：

有 8 万元的投资可以投给3 个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。

投资额

盈利

项目

0

1

2

3

4

5

6

7

8

项目1 0 5 15 40 80 90 95 98 100

项目2 0 5 15 40 60 70 73 74 75

项目3 0 4 26 40 45 50 51 52 53

请安排投资计划，使总的利润最大。

写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步

骤及结果。

设状态变量kx表示投资给项目k至项目n的投资额。

决策变量ku表示投资给项目k的投资额，则状态转移方程为：1kkkxxu 其中1kx表示投资给项目1k至项目n的投资额。

允许决策集合：(){|0}kkkkkDxuux

()kkfx表示把kx的钱投资给项目k至项目n，盈利的最大额。

递推关系式：

其中()kkgu表示上表格中项目k的投资额为ku时盈利。

10()max{()()}1,......,1()()kkkkkkkkkuxnnnnfxgufxuknfxgx针对这个例子，3n，kx最大取8

手工详解过程：

1）初始化3k

333333333(0)0;(1)4;(2)26;(3)40;(4)45;(5)50;(6)51;(7)52;(8)53fffffffff

2）2k

223223232232323223232323(0)max{(0)(0)}0(1)max{(0)(1),(1)(0)}max{04,50}5(2)max{(0)(2),(1)(1),(2)(0)}max{026,54,150}26(3)max{(0)(3),(1)(2),(2)(1),(3)(0)}fgffgfgffgfgfgffgfgfgfgf2232323232322323232323max{040,526,154,400}40(4)max{(0)(4),(1)(3),(2)(2),(3)(1),(4)(0)}max{045,540,1526,404,600}60(5)max{(0)(5),(1)(4),(2)(3),(3)(2),(4)(1)fgfgfgfgfgffgfgfgfgfgf232232323232323232,(5)(0)}max{050,545,1540,4026,604,700}70(6)max{(0)(6),(1)(5),(2)(4),(3)(3),(4)(2),(5)(1),(6)(0)}max{051,550,1545,4040,6026,704,730}86(7)mgffgfgfgfgfgfgfgff232323232323232322323232ax{(0)(7),(1)(6),(2)(5),(3)(4),(4)(3),(5)(2),(6)(1),(7)(0)}max{052,551,1550,4045,6040,7026,734,740}100(8)max{(0)(8),(1)(7),(2)(6),gfgfgfgfgfgfgfgffgfgfgfg32323232323(3)(5),(4)(4),(5)(3),(6)(2),(7)(1),(8)(0)}max{053,552,1551,4050,6045,7040,7326,744,750}110fgfgfgfgfgf3）1k

动态规划 2

动态规划 2

资源分配（P171例25）

姓名：李广灿 学号：201003010099 班级：10计科应用

一、问题描述

现有7万元投资到A，B，C 三个项目，利润见表,问题：求总利润最大的资源分配方案。

二、算法设计

3个项目的投资、利润之间都是不独立的，因此不可能用分治算法来完成。同样也找不到一种能由局部信息得到唯一解困的决策策略，也就是说不能用贪婪算法解决该问题。因此应该通过动态规划法来尽兴算法设计。

1、阶段划分及策略

比较直观的阶段划分是逐步考虑每一个项目在不同投资额下的利润情况。每个阶段要考虑各种分派方案下的最大利润，设fi(x）为将资源x分配给前i个项目所得到的最大利润，分阶段策略过程是：

f1(x)=g1(x) 0≤x≤n;

fi(x)=max{gi(z)+fi-1(x-2)} 0≤x≤n i=2,3,4„n

由于每一阶段都考虑了所有的投资组合情况，所以算法策略是满足最佳原理的。

2、实例

1）考虑分配给第一个项目A的资金x与利润f1（x）的关系

2）考虑分配给前两个项目A，B的总资金为x（0≤x≤n），资金x与利润f2（x）的关系

3）考虑投入7万元的、资金给A，B，C3个项目，利润与资金的关系。

三、数据结构设计 项额 1 2 3 4 5 6 7

A 0.11 0.13 0.15 0.21 0.24 0.30 0.35

B 0.12 0.16 0.24 0.23 0.25 0.24 0.34

C 0.08 0.12 0.20 0.24 0.26 0.30 0.35 （1）由于利润表是逐行使用的，所以不必要开辟二维数组，只需开辟n个元素的一位数组q来存储原始数据。

（2）另开辟的、n个元素的一位数组f存储当前最大收益情况。

（3）在动态规划的过程中，当处理完成第i个项目，读入第i-1个项目的利润情况后，要计算新的最大收益时，第i个项目的最大收益情况要被、重新利用，也就是说数组f的值不能边处理边覆盖。所以要开辟记录中间结果的n个元素的一维数组temp，记录正在计算的最大收益。