干货分享丨动态规划十问十答

简介: 动态规划十问十答,带你扫盲DP

动态规划是IT技术面试中最难的算法,很多人披荆斩棘,最终还是跪在动态规划题目上。

今天给大家总结动态规划十问十答,快速帮你扫盲动态规划。

问1
动态规划是个什么鸟蛋?

答:动态规划是一种通过“大而化小”的思路解决问题的算法。区别于一些固定形式的算法,如二分法,宽度优先搜索法,动态规划没有实际的步骤来规定第一步做什么第二步做什么。
所以更加确切的说,动态规划是一种解决问题的思想。
这种思想的本质是,一个规模比较大的问题(假如用2-3个参数可以表示),是通过规模比较小的若干问题的结果来得到的(通过取最大,取最小,或者加起来之类的运算)所以我们经常看到的动态规划的核心——状态转移方程都长成这样:

  • fi = fi - 1 + fi
  • f[i] = max{f[j] if j < i and …} + 1
  • fi = f0 && judge(1,i) || f1 && judge(2,i) || …

问2
动态规划面试考得多么?

答:多。并且越来越多。随着CS从业与求职者的增加,并伴随大家都是“有备而来”的情况下,一般简单的反转链表之类的题目已经无法再在面试中坚挺了。因此在求职者人数与招聘名额的比例较大的情况下,公司会倾向于出更难的面试问题。而动态规划就是一种比较具有难度,又比较“好出”的面试问题。相比其他的算法与数据结构知识来说,贪心法分治法太难出题了,搜索算法往往需要耗费求职者过长的程序编写时间一般也不倾向于出,二叉树链表等问题题目并没有那么多,而且求职者也都会着重准备这一块。因此动态规划这一类的问题,便越来越多的出现在了面试中。

问3
动态规划快在哪儿?

答:动态规划一般来说是“高效”的代名词,因为其解决的问题一般退而求其次的算法只有搜索了。以“数字三角形”一题为例子。

在“三角矩阵”中找一条从上到下的路径,使得权值之和最小。如果使用暴力搜索的算法,那么需求穷举出2^(n-1)条路径(n为三角形高度),而使用动态规划的话,则时间复杂度降低到了n^2,完成了质的飞跃。

那么究竟为什么这么快呢?原因在于动态规划算法去掉了“无用和重复的运算”。在搜索算法中,假如从A->B有2条路径,一条代价为10,另外一条代价为100,B->终点有1024条路径。当我们选择了代价为10的那条路径走到B时,可以继续往下走完1024条路径到终点,但是在此之后,我们再从代价为100的路径从A走到B时,我们可以发现此时无论如何走,都不可能有刚才从10的路径走过来更好,所以这些计算是“无用”的计算,也可以说是“重复”的计算。这就是动态规划之所以“快”的重要原因。

**
问4**
学习动态规划有什么捷径?

答:我们将动态规划的常见类型分为如下几种:

  • 矩阵型
  • 序列型
  • 双序列型
  • 划分型
  • 区间型
  • 背包型
  • 状态压缩型
  • 树型

其中,在技术面试中经常出现的是矩阵型,序列型和双序列型。划分型,区间型和背包型偶尔出现。状态压缩和树型基本不会出现(一般在算法竞赛中才会出现)。

每种类型都有着自己的题目特点和状态的表示方法。以矩阵型动态规划为例,一般题目会给你一个矩阵,告诉你有一个小人在上面走动,每次只能向右和向下走,然后问你比如有多少种方案从左上走到右下

这种类型状态表示的特点一般是使用坐标作为状态,如fi表示走到(i,j)这个位置的时候,一共有多少种方案。状态的转移则是考虑是从哪儿走到(i,j)这个坐标的。而序列型的动态规划,一般是告诉你一个序列;双序列的动态规划一般是告诉你两个字符串或者两个序列。

将所做过的动态规划问题按照这些类别进行归类,分析状态的表示方法和状态转移方程的构造方法在每种类型中的近似之处,会让你更快的学会动态规划。

更多内容请参考九章算法《动态规划专题班》

问5
什么样的问题适合使用动态规划?

答:可以使用动态规划的问题一般都有一些特点可以遵循。如题目的问法一般是三种方式:

  1. 求最大值/最小值
  2. 求可不可行
  3. 求方案总数

如果你碰到一个问题,是问你这三个问题之一的,那么有90%的概率是使用动态规划来求解。

要重点说明的是,如果一个问题让你求出“所有的”方案和结果,则肯定不是使用动态规划。

问6
解决一个动态规划问题的步骤是什么?

答:首先根据“问5”判断是否是动态规划的问题,如果是,则尝试将其按照“问4”进行分类,找到对应的类别和相似的问题。接着从下面的4个要素去逐步剖析解决这道题:

  1. 状态是什么
  2. 状态转移方程是什么
  3. 状态的初始值是什么
  4. 问题要求的最后答案是什么

每个步骤分析完成之后,就基本上解决了整道动态规划的问题。

问7
怎样优化动态规划的时间?

答:一般来说,使用动态规划求解的问题,时间上已经比暴力搜索要优化很多了。但是仍然存在着一些可以优化的空间。通常来说,动态规划的时间优化,有如下两种常见的方式:

  1. 通过变换状态优化
  2. 通过决策单调优化

对于通过变换状态来优化的问题比较难,需要一些经验和灵感。而对于决策单调的优化,则比较简单,但适用范围不广,一般只适用于划分型动态规划当中,通常这个方法可以将复杂度降低一个数量级。

**
问8**
怎样优化动态规划的空间?

答:动态规划的空间优化只有一种方法,就是使用滚动数组进行优化。以一个二维的动态规划为例子。假如状态转移方程如下:fi = fi - 1 + fi。我们可以发现,第i层的状态,已经和第i-2层的状态没有关系了,那么这种情况下,用于存储第i-2层的空间就可以被重复利用。方法非常简单,把数组的第一维对2取模就可以了:fi % 2 = f(i - 1) % 2 + fi % 2。这种方法通常可以将空间复杂度降低一个数量级。

问9
有哪些动态规划题目必须要练习的?

在 LintCode 上包含了80余道动态规划的练习题

都是从实际的面试问题中汇总的精选练习,熟练掌握这些练习题,基本上可以满足面试需求。

问10
有什么参考资料可以推荐么?

九章算法《动态规划专题班》

相关文章
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1651 1
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
3007 0
|
19天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8498 58
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3025 9
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5808 69
|
7天前
|
云安全 人工智能 安全
|
11天前
|
人工智能 安全 API
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(dsh)是DeepSeek AI于2026年开源的轻量级Agent运行框架,基于Cordis内核,践行“一切皆插件”理念。支持Web/桌面双端,开箱即用;内置多模型接入、丰富插件生态(超3.5万),适配编程、办公、创作等场景。(239字)
1912 1