动态规划基础水题提纲

灰太狼 2022-04-22 11:02 152阅读 0赞

提纲

汉诺塔

**汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根**[**金刚石**][Link 1]**柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。**

**动态规划：**

**1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。**

**2) 无后效性。当前的若干个状态值一旦确定，则此后过程 的演变就只和这若干个状态的值有关，和之前是采取哪 种手段或经过哪条路径演变到当前的这若干个状态，没 有关系。**

**例子：**

**7**

**3 8**

**8 1 0**

**2 7 4 4**

**4 5 2 6 5**

**在上面的数字三角形中寻找一条从顶部到底边的路径，使得 路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。**

**---------------------**

### **把原问题分解为若干个子问题，子问题和原问题形式相同 或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。** ###

**1）****有一只兔子，从出生后第****2****个月起每个月都生一只兔子，小兔子长到第****2****个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？**

**2）****有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？**

**3）****有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？**

**4）****我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？**

##  ##

1.  **一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。**

**6）****一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。**

**7）****有一个X\*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。**

**推荐读物:**

**背包问题**

**背包九讲**

[Link 1]: https://baike.baidu.com/item/%E9%87%91%E5%88%9A%E7%9F%B3/80698

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划理论基础

什么是动态规划 -------------------- 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是

川长思鸟来/ 2024年03月27日 14:29/ 0 赞/ 88 阅读

相关动态规划理论基础

动态规划理论基础刷题大纲动态规划的定义动态规划的解题步骤动态规划五部曲动态规划应该如何debug 刷题大纲 ![在这

￡神魔★判官ぃ/ 2023年10月16日 15:48/ 0 赞/ 22 阅读

相关动态规划刷题

分金子（360公司2017春招真题）题目链接 https://exercise.acmcoder.com/online/online\_judge\_ques?q

红太狼/ 2023年07月18日 06:58/ 0 赞/ 38 阅读

相关基础算法题——nico和niconiconi（动态规划）

nico和niconiconi（动态规划）前言本人为一名普通二本学校自动化专业的大二学生，对编程有着少许兴趣。动态规划有时候真的挺摸不着头绪的，希望这道题

短命女/ 2023年07月13日 10:40/ 0 赞/ 13 阅读

相关动态规划题 leetcode

1. [62. 不同路径][62.] 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人

我不是女神ヾ/ 2022年12月27日 08:51/ 0 赞/ 235 阅读

相关动态规划刷题总结

题目1：输出描述: 对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。输入例子: 2 7 89 256 7

逃离我推掉我的手/ 2022年09月24日 15:28/ 0 赞/ 220 阅读

相关动态规划算法题总结

一.动态规划的基本思想 > 动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过

缺乏、安全感/ 2022年05月17日 08:57/ 0 赞/ 233 阅读

相关动态规划基础水题提纲

提纲汉诺塔汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根[金刚石][Link 1]柱子，在一根柱子上从下往上按照大小顺序

灰太狼/ 2022年04月22日 11:02/ 0 赞/ 153 阅读

相关 leetcode 动态规划类型题

1，Triangle ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 1 int mininumTotal

怼烎@/ 2021年12月03日 08:10/ 0 赞/ 292 阅读

相关 hdu 2546 饭卡-动态规划（基础中的基础题）

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负

布满荆棘的人生/ 2021年09月30日 04:24/ 0 赞/ 233 阅读