技术

数据湖 高性能计算与存储 Linux2.1.13网络源代码学习 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器以及defer实现 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go堆内存分配 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 递归、回溯、动态规划 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型和jvm内存布局 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM执行 git maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

架构

controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群及clusternet学习 AutoML和AutoDL 特征平台 实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 从混部到统一调度 RNN pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台梳理 tf-operator源码分析 k8s批处理调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Admission Controller 与 Admission Webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 概率论 serverless 泛谈 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念入门 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 当我在说模板引擎的时候,我在说什么 用户认证问题 资源的分配与回收——池 消息/任务队列

标签

controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群及clusternet学习 helm 从混部到统一调度 volcano特性源码分析 kubebuilder 学习 client-go学习 tf-operator源码分析 k8s批处理调度 喜马拉雅容器化实践 Kubernetes 实践 openkruise学习 基于Kubernetes选主及应用 Admission Controller 与 Admission Webhook k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? Kubernetes events学习及应用 CRI 资源调度泛谈 如何学习Kubernetes 以应用为中心 kubernetes operator kubernetes扩缩容 serverless 泛谈 自定义CNI IPAM docker和k8s安全访问机制 Kubernetes监控 Kubernetes 控制器模型 Kubernetes资源调度——scheduler Kubernetes类型系统 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 Kubernetes源码分析——从kubectl开始 kubernetes yaml配置 CNI——容器网络是如何打通的 当我在说PaaS时,我在说什么 《深入剖析kubernetes》笔记 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件

递归、回溯、动态规划

2017年10月11日

简介

笔者最近在和同事准备校招题的时候,有一道涉及到回溯的编程题,发现自己也不会,看了答案也没什么感觉,因此收集材料整理下。

本文涉及到两道题目:

  1. 利用字符‘a’、‘b’ 、 ‘c’ 、‘d’ 、‘e’ 、‘f’、‘g’生成并输出所有可能的字符串(但字符不可重复使用,输出顺序无要求),比如: “a”、“b”、“c”、“d”、“e”、“f”、“g”、“ab”、“ba”、“ac”、“ca”
  2. 集合A的幂集是由集合A的所有子集所组成的的集合,如:A=1,2,3,则A的幂集P(A)={1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{ },求一个集合的幂集就是求一个集合的所有的子集。来自回溯法求幂集

两个问题基本一样,主要是回溯法求幂集 对回溯法的一些思路表述的比较精彩。下文会混用两个问题。

重新理解递归

写递归函数的正确思维方法基本要点:

  1. 递归算法采用的是分治的思想,把一个大问题分解为若干个相似的子问题求解。
  2. 看到一个递归实现, 我们总是难免陷入不停的回溯验证之中(把变量的变化依次写出来), 因为回溯就像反过来思考迭代,这是我们习惯的思维方式, 但是其实无益于理解。数学归纳法才是理解的递归的方式,函数式编程也有这么点意思。
  3. 递归并不是算法,它是和迭代对应的⼀种编程⽅法。只不过,我们通常借 助递归去分解问题⽽已。对于f(n) = max(f(n-1),f(n-2)) 可以用递归写,也可以用 用迭代 从f(0) f(1) 一直求到f(n),迭代的空间复杂度更低一些。递归就是自我调用,经常作为一种编程的实现方式,DFS 、动态规划、回溯法都可以用递归来实现,当然也可以用非递归来实现。
  4. 如果你刚开始接触递归,⼀个简 单练习递归的⽅式是将你写的迭代全部改成递归形式。⽐如你写了⼀个程 序,功能是“将⼀个字符串逆序输出”,那么使⽤迭代将其写出来会⾮常容 易,那么你是否可以使⽤递归写出来呢?通过这样的练习,可以让你逐步 适应使⽤递归来写程序。

基本思路

  1. 定义递归函数功能。尤其是参数和返回值的选择,dfs 下传哪些信息(参数或全局变量)以便子节点做判断:有几个分叉,是否可以终止,如何剪枝。
  2. 找出递归结束的条件。当我们处理递归问题时, 如何定义递归出口是非常重要的一步。递归出口是递归函数 可以直接处理的最简单子问题。请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。或者说,只要你觉得参数是什么时,你能够直接知道函数的结果,那么你就可以把这个参数作为结束的条件。一把有关树的DFS 问题,递归出口都是叶子节点或空节点,然后基于叶子节点/空节点 判断当前路径是否符合要求。
  3. 找出函数的等价关系式。我们要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。

递归中如果存在重复计算(称为重叠⼦问题),那就是使 ⽤记忆化递归(或动态规划)解题的强有⼒信号之⼀。可以看出动态规划 的核⼼就是使⽤记忆化的⼿段消除重复⼦问题的计算,如果这种重复⼦问 题的规模是指数或者更⾼规模,那么记忆化递归(或动态规划)带来的收 益会⾮常⼤。为了消除这种重复计算,我们可使⽤查表的⽅式。即⼀边递归⼀边使⽤ “记录表”(⽐如哈希表或者数组)记录我们已经计算过的情况,当下次再 次碰到的时候,如果之前已经计算了,那么直接返回即可,这样就避免了 重复计算。

回溯法

回溯法是一种复杂度很高的暴力搜索算法 ,时间复杂度是O(2^n)。 不同于普通的暴力搜索,回溯法会在每一步判断状态是否合法,而不是等到状态全部生成后再进行确认。当某一步状态非法时,它将回退到上一步中正确的位置,然后继续搜索其它不同的状态。前进和后腿是回溯法的关键动作,因此可以使用一个递归函数去模拟整个搜索过程,即使用递归实现回溯法。很多时候每一步的处理都是一致的,这时候用递归来实现就很自然。

回溯法采⽤ 试错 的思想,它尝试分步的去解 决⼀个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上⼀步甚⾄是上⼏步的计 算,再通过其它的可能的分步解答再次尝试寻找问题的答案。 通俗上讲,回溯是⼀种⾛不通就回头的算法。回溯算法强调了「深度优先遍历」思想的用途,当回溯用于树的时候,就是深度优先搜索DFS,借助系统栈空间,保存所需要的状态变量。当然了,几乎所有可以用回溯解决的问题都可以表示为(要学会用树辅助分析)。那么这俩在这里就几乎同义了。

回溯的本质是穷举所有可能,尽管有时候可以通过剪枝去除⼀些根本不可 能是答案的分⽀, 但是从本质上讲,仍然是⼀种暴⼒枚举算法。回溯法可以抽象为树形结构,并且是是⼀颗⾼度有限的树(N 叉树)。回溯法解决的都是在集合中查找⼦集,集合的⼤⼩就是树的叉数,递归的深 度,构成树的⾼度

PS:与dp 类似, 回溯也是有方向的,对于字符串、数组问题,有时候是从前向后回溯,有时候则是从后向前回溯(比如连续字串问题,从前向后 不能继续推导的)。

算法模板

// 有时候仅仅是向下层传递 i 是不够的,还应透传更多状态,下传哪些信息以便子节点做决策?终止条件、分支个数等
const visited = {}      // 记录访问过的路径,回溯发标配
function dfs(i) {       // i 表示当前走到哪里了
    if (满⾜特定条件){ // 找到可行解提前结束搜索;搜索完毕,已经没有可搜索的解空间
        // 返回结果 or 退出搜索空间
    }
    visited[i] = true   // 将当前状态标为已搜索
    dosomething(i)      // 对当前节点i做⼀些操作
    for (根据i能到达的下个状态j) {      // for 循环⽤来枚举分割点
        if (!visited[j]) {          // 如果状态j没有被搜索过
            dfs(j)
        }
    }
    undo(i) // 恢复i 
}

除了业务有特性可以利用外,回溯树一般前进到 叶子的左右(都是nil)孩子才会终止,需要注意:

function dfs(root *TreeNode) xx { 
    if root == nil {    // 终止条件
        // 此时要注意的是,叶子的left right 都为nil ,都会执行到这里,会被执行两次
        return xx
    }
    // 对当前node 进行处理
}

回溯的本质就是暴⼒枚举所有可能。要注意的是,由于回溯通常结果集都 记录在回溯树的路径上,因此如果不进⾏撤销操作, 则可能在回溯后状 态不正确导致结果有差异, 因此需要在递归到底部往上冒泡的时候进⾏ 撤销状态。

回溯题⽬的⼀个考点是剪枝, 通过恰当地剪枝,可以有效减少时 间,剪枝在每道题的技巧都是不⼀样的

  1. ⼀个简单的原则就是避免根本不可能是答案的递归
  2. 根据问题的特性,调整分叉的顺序,使得每次尝试的“路径”都是概率最大的,以便尽早结束对当前节点其它分叉的遍历,但因为问题的特性很难全部掌握,概率最大的分叉也有失败的可能,所以会有“回溯”的动作。

动态规划

如果求从一个tree 从root 到所有leaf 路径的最大和(每一个node 有一个int),只能用回溯法(此时的回溯只是遍历树的手段),说白了就是遍历所有路径,路径没有遍历完,不能确定哪个最大。但是求一个矩阵从左上角到右下角 所有可选路径(假设只能向右或向下)哪个最大,则可以使用动态规划,因为到达右下角之前,一定会到达“右下角” 上边或左边的点。

为什么动态规划会快一点

动态规划和其它算法思想如递归、回溯、分治、贪心等方法都有一定的联系,其背后的基本思想是枚举,虽然看起来简单, 但如何涵盖所有可能,并尽可能重叠子问题的计算是一个难点。与回溯法的暴力枚举不同(刷leetocode,很多题上来就用递归做肯定能做出来,但超时了),动态规划法的枚举是没有重复的,这种不重复建立在巧妙的利用之前计算过的结果集上。然而想利用之前计算过的结果集,就需要对问题进行分解,因此动态规划法都会涉及对原问题进行分解的过程。大致上, 若要解决一个给定问题, 我们需要解决其各个部分(即子问题),再根据子问题的解得出原问题的解。

  1. 动态规划的本质是将大问题转化为小问题,并且大问题的解和小问题是有关联的。
  2. 动态规划算的本质使用空间换时间,通过计算和记录状态来得到最优解。其实大部分动态规划问题都是“选择”和“不选择”的问题,比如背包问题就是“装”还是“不装”,选择的标准就是看哪种选择带来的价值更大,因此我们要做的就是对于选择和不选择两种情况分别求值,然后取最大者。比如爬楼梯问题,dp[i] = dp[i-1] + dp[i-2],此处的i 是越来越大, 最终目的是计算f(n);也有的i 是越来越小,最终目的是计算 dp[0]转换公式本质是一种对遍历的加速,也就是dp[i] 需要一个复杂的公式算一下,现在直接可以通过 dp[i-1]dp[i-2] 计算而来。回溯法因为每次只考虑当前路径,面对“选择”,只能先选一条路走到底。而动态规划,是在dp[i-1]dp[i-2] 的基础上决定dp[i],选择的背景信息已经确定了,做决定即可。
  3. 因为大部分动态规划问题都是“选择”和“不选择”的问题,所以这些问题一般无法用o(n)方法解决。因此o(n) 只遍历一遍,如果根据当前状态 (最多加上之前遍历得到的一些信息)无法做出选择,就只能求助于o(nlogn) 或o(n^2) 算法了。

定义状态

动态规划最重要的两个概念:最优⼦结构和⽆后效性。

  1. ⽆后效性决定了是否可使⽤动态规划来解决。即⼦问题的解⼀旦确定,就不再改变,不受在这之后、包含它的更⼤的问 题的求解决策影响。背包问题中选择是否拿第三件物品,不应该影 响是否拿前⾯的物品。⽐如题⽬规定了拿了第三件物品之后,第⼆件物品的价值就会变低或变⾼。这种情况就不满⾜⽆后向性。
  2. 最优⼦结构决定了具体如何解决。DP 数组也可以叫”子问题数组”。一个子问题的解要能通过其他子问题的解求出,在整个问题的每一个子问题得到的答案都是最优的。一些问题 无法建立 f(n) 与 f(1) 到f(n-1) 关系,此时可能是因为该问题无法使用动态规划,或许是因为 子问题的定义有问题。

动态规划的中⼼点是什么?那就是定义状态。定义好了状态,就可以画出递归 树,聚焦最优⼦结构写转移⽅程就好了,因此我才说状态定义是动态规划 的核⼼,动态规划问题的状态确实不容易看出。⽐如⼀个字符串的状态,通常是 dp[i]表示字符串 s 以 i 结尾的 ….。 ⽐如两个字符串的状态,通常是 dp[i][j] 表 示字符串 s1 以 i 结尾,s2 以 j 结尾的 ….。

每一个动态规划问题,都可以被抽象为一个数学函数,这个函数的自变量集合就是题目的所有取值,值域就是题目要求的答案的所有可能。我们的目的就是填充这个函数的内容,使得给定自变量x 能够唯一映射到一个值y。当然自变量可能有多个,要求是能将所有“选择”都描述到(动态规划就是不断在状态间做选择),最终x 的某个边界值就是我们要的解。

经典动态规划问题(理解「无后效性」)设计状态思路:把不确定的因素确定下来,进而把子问题定义清楚,把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题,进而把简单的问题的解组成了复杂的问题的解。比如“最大子序列和问题”,我们 不知道和最大的连续子数组一定会选哪一个数,那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。

例如,示例 1 输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ,我们可以求出以下子问题:

  1. 子问题 1:经过 -2 的连续子数组的最大和是多少;
  2. 子问题 2:经过 1 的连续子数组的最大和是多少;
  3. 子问题 3:经过 -3 的连续子数组的最大和是多少;
  4. 子问题 4:经过 4 的连续子数组的最大和是多少;
  5. 子问题 5:经过 -1 的连续子数组的最大和是多少;
  6. 子问题 6:经过 2 的连续子数组的最大和是多少;
  7. 子问题 7:经过 1 的连续子数组的最大和是多少;
  8. 子问题 8:经过 −5 的连续子数组的最大和是多少;
  9. 子问题 9:经过 4 的连续子数组的最大和是多少。

一共 9 个子问题,这些子问题之间的联系并没有那么好看出来,这是因为 子问题的描述还有不确定的地方。这件事情叫做「有后效性」

例如「子问题 3」:经过 -3的连续子数组的最大和是多少。「经过 -3 的连续子数组」我们任意举出几个:

[-2,1,-3,4] ,-3 是这个连续子数组的第 3 个元素; [1,-3,4,-1] ,-3 是这个连续子数组的第 2 个元素; ……

我们不确定的是:−3 是连续子数组的第几个元素。那么我们就把 −3 定义成连续子数组的最后一个元素。在新的定义下,我们列出子问题如下:

  1. 子问题 1:以 -2 结尾的连续子数组的最大和是多少;
  2. 子问题 2:以 1 结尾的连续子数组的最大和是多少;
  3. 子问题 3:以 −3 结尾的连续子数组的最大和是多少;
  4. 子问题 4:以 4 结尾的连续子数组的最大和是多少;
  5. 子问题 5:以 −1 结尾的连续子数组的最大和是多少;
  6. 子问题 6:以 2 结尾的连续子数组的最大和是多少;
  7. 子问题 7:以 1 结尾的连续子数组的最大和是多少;
  8. 子问题 8:以 −5 结尾的连续子数组的最大和是多少;
  9. 子问题 9:以 4 结尾的连续子数组的最大和是多少。

我们加上了「结尾的」,这些子问题之间就有了联系。我们单独看子问题 1 和子问题 2:

子问题 1:以 −2 结尾的连续子数组的最大和是多少;

以 −2 结尾的连续子数组是 [-2],因此最大和就是 −2。

子问题 2:以 1 结尾的连续子数组的最大和是多少;

以 1 结尾的连续子数组有 [-2,1] 和 [1] ,其中 [-2,1] 就是在「子问题 1」的后面加上 1 得到。-2 + 1 = -1 < 1 ,因此「子问题 2」 的答案是 1。

因为我们把子问题定义的更清楚,子问题之间的联系就容易观察到。这是我们定义子问题、定义状态的经验。解决「有后效性」的办法是固定住需要分类讨论的地方,记录下更多的结果。在代码层面上表现为:

  1. 状态数组增加维度,例如:「力扣」的股票系列问题;
  2. 把状态定义得更细致、准确,例如:前天推送的第 124 题:状态定义只解决路径来自左右子树的其中一个子树。

注意:此时最后一个状态值只表示以 nums[len - 1] 结尾的子数组和,状态数组 dp 的最大值才是题目要求的结果。

另一种定义状态的经验:动态规划问题都可以用回溯法求解(动态规划也是一种暴力枚举,只不过加速了枚举过程),回溯法经常可以使用记忆化递归优化性能,递归时一般要向下层递归函数传递当前状态,这个状态就是 状态转移方程用到的状态。PS:解题时,如果实在想不明白动态规划,可以使用记忆化递归求解。

  1. 一个自变量对应一维dp,两个自变量对应二维dp(三维dp 一般碰不到,碰到了直接放弃吧)。从另一个角度说,用一维dp解决的 可以用两个一维dp解决,也可以用二维dp解决,比如一些子序列问题dp[i] 等同于dp[0][i],但如果没有 dp[i][j] 与 dp[i+1][j-1] 的关系的话(从中间推两端),用一维dp 就ok了。
  2. 二维dp 两个自变量有时候表示 字符串的首尾,但有时候从问题中抽取,比如背包问题,dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少)。⽐如两个字符串的状态,通常是 dp[i][j] 表 示字符串 s1 以 i 结尾,s2 以 j 结尾的
  3. 动态规划时间复杂度经常无法优化了(毕竟遍历dp是省不了的),有时候可以从状态数组 dp入手 优化空间复杂度,比如将二维dp 优化为两个一维dp,甚至优化为一个一维dp(比如01背包问题)。
  4. 最神奇的一个搞法:记录一个数组 部分元素和,假设数组长度为n,用一个 0~n-1 位来表示 数组的某个元素是否被选中,S=01001 表示 数组第2 和第5个元素被选中,dp[S] 记录此时的结果。

有时dp 数组最后一个值(比如dp[len-1])不一定是答案,答案可能是dp[0](打家劫舍问题),dp 数组的最大值或最小值(乘积最大子数组)。有的时候只需要返回dp的值即可(比如返回最长xx的长度),但有时也要返回“最长xx”本身,此时dp 值可能是布尔值,最后结果可以是 j-i 的最大值。

状态转移

当你定义好了状态,剩下就三件事了:

  1. 临界条件; 比如⼀个⼈爬楼梯,每次只能爬 1 个或 2 个台阶,假设有 n 个台阶,那么这 个⼈有多少种不同的爬楼梯⽅法?如果我们⽤ f(n) 表示爬 n 级台阶有多少种⽅ 法的话,f(1) 与 f(2) 就是【边界】,f(n) = f(n-1) + f(n-2)/dp[i] = dp[i-1] + dp[i-2] 就是【状态转移公式】。
  2. 状态转移⽅程;动态规划中当前阶段的状态往往是上⼀阶段状态和上⼀阶段决策的结果。也就是说,如果给定了第 k 阶段的状态 s[k] 以及决策 choice(s[k]),则第k+1 阶段的状态 s[k+1] 也就完全确定,⽤公式表示就是:s[k] +choice(s[k]) -> s[k+1], 这就是状态转移⽅程。需要注意的是 choice 可能 有多个,因此每个阶段的状态 s[k+1]也会有多个。通过状态转移方程减小问题规模
  3. 枚举状态。 推导公式估计看一遍就记下来了,但难就难在如何初始化和遍历顺序上。一些场景下,遍历顺序取决于状态转移⽅程:正推、反推。⽐如下面代码 我们就需要从左到右遍历,原因很简单,因为 dp[i] 依赖于 dp[i - 1], 因此计算 dp[i] 的时候, dp[i - 1] 需要已经计算好了。
     for i in range(1, n + 1):
         dp[i] = dp[i - 1] + 1
    

状态转移方程不一定都是dp[i]dp[i-1]的方程(实质跟枚举类似),尤其是对于一些不连续的问题,dp[i]dp[i-1]不一定能建立直接的推导关系,有时候dp[i] = max(dp[0]..dp[i-1]),有时候dp[i] = dp[j] && judge(i,j) 等等。PS:想不出来,就老老实实用回溯吧

更一般的说,状态转移方程是 建立 dp[i]dp[j] 的关系(j 满足一定条件),以便根据 dp[j] 计算 dp[i]。此时出现了一个需要解决的问题,如何保证在处理到位置 i 时,所有满足条件的位置 j 都已经被处理过了呢?

  1. 如果j 在i 的一侧,可以根据位置从小到大或者从大到小进行动态规划
  2. 如果j 分布在位置 i 的两侧,可以借助记忆化搜索的方法,即当我们需要 dp[j] 的值时,如果我们之前已经计算过,就直接返回这个值(记忆);如果我们之前没有计算过,就先将 dp[i] 搁在一边,转而去计算 dp[j](搜索),当 dp[j] 计算完成后,再用其对 dp[i] 进行状态转移。

如果从 状态转移方程的视角 看动态规划,状态转移方程也要在 for 循环里,也是迭代,只是迭代公式更复杂。

  1. 线性动态规划,s[k] +choice(s[k]) -> s[k+1]
  2. 区间动态规划,f(i,j)=max{f(i,k)+f(k+1,j)+cost}

递归/回溯/动态规划对比

dfs 带不带返回值

有两种习惯

  1. dfs 只负责遍历,树的分叉几乎都会遍历,路径信息(比如path 新增元素与删除)代表了遍历的路径, 基本逻辑:状态扩充 + dfs 下探 + 状态回退,然后考虑 在回溯的模板上 加上 对当前节点/当前已遍历路径 的处理。谈不上什么回溯 或没有回溯,直到递归终止,此时得到了一个完整的路径,计算最大值、最小值、记录所有可行解。前序遍历。
  2. 通过返回值 感知到 子节点/子问题的结果。PS:其实这个返回值如果 不使用的话,就跟第一种情况一样了。后序遍历。
    1. 一种场景:尽早结束对当前节点其它分叉的遍历。前提是 子节点根据 下传给递归函数的信息 或全局信息 或仅凭自己的信息 就可以判断出子问题的结果。一般在递归 终止条件的地方,此时得到了一个完整的路径(如果有的话),判断当前路径是否满足解的要求(比如路径上所有节点的和为target)。继而父节点拿到子节点的返回值,判断是否还有执行下一个分叉的必要。
    2. 一种场景,解决问题本来就是要求 从下到上的 先拿到子节点的结果,比如求树上所有节点的和。
  3. 中间状态的记录,可以通过全局变量(一般对应数组这种情况,go slice 值传递会丢失自动扩容后指针),也可以都通过 递归参数传递
  4. 典型问题如“基于数组 nums=[2,3,1]构造一个小于n=23231的最大数”,答案为23222。PS:第一次碰到的时候,没有想过这是一个dfs问题
    1. 暴力 遍历数组的所有子序列(长度为5,元素可重复),用一个全局变量max记录 小于n的最大值。不遍历完,max 就可能不对。一点剪枝都没有,也不回溯(碰到不可能的解也会一条道走到黑)。
    2. 针对暴力法,可以优化的点是,每个分叉其实 就三个可能:和当前位相等的,仅小于当前位的,0(也就是当前位不选)。后两种其实是一种情况:选择的位数小于当前位/不相等,一旦小于当前位,后面的位全部以最大值填充即可。如果前面的位数 与n 都相等,但nums 中没有比当前位小的元素,则此路不通,回溯树回退。核心是 通过删掉不可能的分叉,调整树的分叉顺序,使得越靠前的“路径”越有可能是最终解。

以爬楼梯为例比较递归和动态规划

⼀个⼈爬楼梯,每次只能爬 1 个或 2 个台阶,假设有 n 个台阶,那么这 个⼈有多少种不同的爬楼梯⽅法?思路: 由于第 n 级台阶⼀定是从 n - 1 级台阶或者 n - 2 级台阶来的,因此到第 n级台阶的数⽬就是 到第 n - 1 级台阶的数⽬加上到第 n - 1 级台阶的数 ⽬ 。

爬楼梯问题的递归写法

function dp(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    return dp(n - 1) + dp(n - 2);
}

爬楼梯问题的动态规划写法,查表,即db table(dynamic_programming),⼀般我们写的 dp table,数组的索引通常对应记忆化递归的函数参数, 值对应递归函数的返回值。

function climbStairs(n) {
    if (n == 1) return 1;
    const dp = new Array(n);
    dp[0] = 1;
    dp[1] = 2;
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[dp.length - 1];
}

滚动数组优化。爬楼梯我们并没有必要使⽤⼀维数组,⽽是借助两个变量来实现的,空间 复杂度是 O(1)

function climbStairs(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    let a = 1;
    let b = 2;
    let temp;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return temp;
}

他们的区别只不过是递归⽤调⽤栈枚举状态, ⽽动态规划使⽤迭 代枚举状态。如果说递归是从问题的结果倒推,直到问题的规模缩⼩到寻常。 那么动态规划就是从寻常⼊⼿, 逐步扩⼤规模到最优⼦结构。动态规划性能通常更好。 ⼀⽅⾯是递归的栈开销,⼀⽅⾯是滚动数 组的技巧。PS: 动态规划不一定写出来是递归。

回溯法与动态规划

  1. 共同点:用于求解多阶段决策问题。
  2. 不同点
    1. 动态规划只需要求我们评估最优解是多少,最优解对应的具体解是什么并不要求。因此很适合应用于评估一个方案的效果;
    2. 回溯算法可以搜索得到所有的方案(当然包括最优解),但是本质上它是一种遍历算法,时间复杂度很高。PS:真的碰到一道题,明明要多个解,也在用dp

建议思路:

  1. 先想递归
  2. 发现重复计算
  3. 通过记忆化等方法弄掉重复计算
  4. 最后看下能不能通过利用计算顺序来做到去掉递归用“刷表”方式直接顺序计算,能搞定最好搞不定拉倒 PS:递归的思维方式更自然一点,除非一眼看出dp怎么做,否则还是别用动态规划。又例如网格问题,上下左右 会搞的dp公式比较复杂。

贪心

贪心算法是指每次根据问题的当前状态,选择一个局部最优策略,并且能够不断迭代,最后产生一个全局最优解。贪心的题目只要求我们想一个合理的局部最优策略,而不需要关注如何证明这个策略能够产生一个全局最优解。

分治

分治法很大程度上也基于递归的思想,两者的区别在于动态规划分解后的子问题是有重复的,而分治法的子问题通常不会重复。 分治法所能解决的问题一般具有以下几个特征。以 “找第K小的数” 的快速选择法来理解下列特征

  1. 问题的规模缩小到一定程度后可以被很容易解决。
  2. 问题可以分解为若干个规模较小的相同性质的问题。快速选择法 将某个范围的数移动到一起,这样子问题的规模才能变小,否则你就只能在子区间找第k个数。
  3. 问题的解等于子问题解的合并。
  4. 问题分解的各个子问题相互独立,没有重复。 PS:curd ==> 查找 ==> 遍历 = 遍历方法 + 判断函数 ==>
  5. 优化遍历方法:直接忽略不可能的解(二分、滑动窗口),可以做到o(n);实在不行,只能分治了。分治也是暴力遍历,但与我们习惯的 for i:=0;i<xxi;i++不同。
  6. 优化判断函数:虽然全遍历但可以缓存判断函数的计算结果o(n^2)。

小结

计算机并没有“大招”,关键是思维不要乱窜。对一些常见题目,掌握的深度也一定要够,不仅要知道得用dp了,还得知道dp的子状态如何定义。