【免费】动态规划dp（常用算法）_动态规划基础版题单资源-CSDN文库

需积分: 0 65 浏览量 2023-07-29 11:59:08 上传评论 1 收藏 46KB DOCX 举报

资源推荐

资源详情

资源评论

动态规划

故事引入

“曾经跨越诸多世界的我，受困于此”，你是一个从世界之外漂流而来的旅行者，你漫

无目的地在这片大陆上探索着，直到你看到了这座石碑：

动态规划简介

古语有云：“尺有所短，寸有所长”，任何算法和思想都有它的局限性。动态规划

（Dynamic Programming，简称 DP）是一种用来解决一类具有重叠子问题（指的是在

求解问题的过程中，会反复求解同一个子问题，导致算法效率低下）和最优子结构性质

（指的是问题的最优解可以通过子问题的最优解来构造，也就是说每一个状态都可以从前

一个状态转移过来）的问题的算法思想。通常采用自底向上的方式，通过将原问题划分为

若干个子问题（分治算法），并先求解子问题的最优解，然后逐步将子问题的解组合起

来，直到求解原问题的最优解。

动态规划问题的解决步骤如下所示：

1.定义状态：定义子问题的解以及问题的解。通常采用状态表示问题的某些属性或特征。

2.确定状态转移方程：确定从一个状态转移到另一个状态的具体方式。

3.初始状态（初始化）：定义最小子问题的解或问题的初始解。

4.计算顺序：根据状态转移方程自底向上计算问题的解。

5.解释解：根据计算得到的解释解决方案。

动态规划之初探

递推

你开始理解石碑上的文字，并好像发现了什么。

走着走着，你登上了几阶楼梯，忽然，你突发奇想：我可以一步跨一级台阶，也可以两

级台阶，那么我有多少种上楼梯的方法呢？

你接受了这个挑战：

题目描述

一段楼梯有 n 级台阶。你每次可以走一级或者走两级。请问走完共有几种方案？

输入格式

剩余17页未读，继续阅读

内容反馈

TangyixiaoQAQ

粉丝: 24
资源: 1

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip