乐趣区

关于算法:动态规划

动静布局

引子 – 爬楼梯

在正式聊动静布局之前,咱们先来看一个经典问题

1. 爬楼梯

假如你正在爬楼梯。须要 n 阶你能力达到楼顶。

每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢?

2. 问题剖析

假如台阶总数为 10,咱们先 不思考 从第 0~ 8 阶的过程,也 不思考 0~9的过程,想要达到第 10 阶,最初一步必然有两个抉择。

 1. 从第 9 个台阶爬 1 阶
 2. 从第 8 个台阶爬 2 阶

接下来引申出一个新问题,如果咱们已知 0~9 阶台阶的走法有 x 种,0-8阶的走法有 y 种,那么达到第 10 阶有多少种走法呢?答案就是 x+y

那达到第 9 个台阶有多少种办法呢?咱们能够依照下面的思路,持续剖析

3. 问题泛化

假如咱们以后处于第 i 个台阶上,依据已知条件,每次只能走 1 或 2 步,所以有两种办法达到第 i 个台阶

 1. 从第 i - 1 个台阶爬 1 阶
 2. 从第 i - 2 个台阶爬 2 阶

假如咱们晓得达到第 i-1 个台阶有 f(i-1) 种办法,达到第 i-2 个台阶有 f(i-2)种办法

若达到第 i-1 个台阶有 f(i-1) 种办法,达到第 i-2 个台阶有 f(i-2)种办法,

则达到第 i 阶有 f(i) 种走法,且等于达到第 i - 1 阶的办法数 f(i-1) 加上达到第 i - 2 阶的办法数f(i-2)

​ 故可得 f(i) = f(i-1)+f(i-2)

上述的过程就是将一个大问题拆解成一个一个的小问题,而后逐层剖析,失去最终后果

其实爬楼梯问题就是一个求解 斐波那契数列 的问题

3. 斐波那契数列的个别解决办法

​ 咱们解决此问题是通过递归形式,从第 n 层一层层递加求出最终后果

func fib(n int) int {
    if n < 0 {return 0} else if n <= 1 {return 1} 
    
    return fib(n-1) + fib(n-2)
}

这里以 5 阶为例

<img src=”https://test-kefu-zs.oss-cn-shenzhen.aliyuncs.com/zjalpha/mobilecheckqualitytool/39fc0af2-2a42-dc6e-64bf-ab936fad7434.png” style=”zoom:50%;” />

从上图能够看出递归解法存在以下缺点:

  1. 标有色彩局部存在反复计算,n 值越大,反复计算越多
  2. 递归层数随着 n 的值变大而加深,会触发零碎最大函数嵌套层
  3. 算法的工夫复杂度为 O(2^n)

那是否有其余办法来解决这个问题呢?是否能够用最开始提到的 动静布局 来解决呢?接下来让咱们一起来理解动静布局,看看是否能解决爬楼梯的问题,以及探讨它与递归的关系

注释 – 动静布局

1. 概念

动静布局(Dynamic Programming 简称 DP):是运筹学的一个分支,是解决 多阶段决策 过程最优化的一种 数学方法。把多阶段问题变换为一系列互相分割的单阶段问题,而后加以解决。

2.DP 能够解决的问题

适宜动静布局的问题必须满足以下条件:

最优子结构:一个最优化策略的子策略总是最优的。

无后效性:问题的历史状态不影响将来的倒退;只能通过以后的状态影响将来;以后的状态是对以往历史的总结

3. 用 DP 解决问题的思路

  1. 状态定义:形容第 i 时刻的状态信息

    1. 找出状态转移方程:找出状态的递推关系式

4. 怎么用 DP 解决爬楼梯(斐波那契数列问题)

1. 状态定义:fib[n]达到第 n 个台阶的总走法

2. 状态转移方程(递推式):达到第 n 阶有两种形式:从 n-1 阶达到,或从 n-2 阶达到,故

fib[n] = fib[n-1] + fib[n-2]

代码如下

func fib(n int) int {
    if n < 0 {return 0}
        // 为了不便大家了解,这里采纳了切片格局,这里其实能够应用两个变量代替 dp[]
    var dp = make([]int, n+1)
    dp[0] = 1
    dp[1] = 1

    for i:=2; i<=n;i++ {dp[i] = dp[i-1]+dp[i-2]
    }

    return dp[n]
}

算法工夫复杂度:O(n)

空间复杂度:O(n),能够优化为 O(1)

看到这里,大家是否发现递归与动静布局的关系

递归和动静布局都是将大问题拆分成多个小问题,动静布局 = 递归 + 记忆化(存储子问题的解)

区别:动静布局是自底向上求解,而递归是自上向下求解

接下来,我再举个栗子


栗子

最小门路和问题

形容:给定一个蕴含非负整数的 m x n 网格 grid,请找出一条从左上角到右下角的门路,使得门路上的数字总和为最小。

阐明:每次只能向下或者向右挪动一步。

剖析

1. 因为题目是求最小门路和,所以咱们 定义状态 dp[i][j] 为在第 ij列时的最小门路和

2. 因为门路的方向只能向下或向右,所以 dp[i][j] 可能的后果就是从以后地位的 上方 dp[i-1][j] 或 左方dp[i][j-1] 过去,所以以后地位的最小门路为 上方或左方的门路中的最小值加上以后地位的值,故可得 状态转移方程

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

根据上述剖析,失去如下代码

func minPathSum(grid [][]int) int {m := len(grid)
    n := len(grid[0])
    var minPath = make([][]int, m+1)

    for i:=0; i<m; i++ {minPath[i] = make([]int, n+1)
    }

    var min int
    for i:=0; i<m; i++ {
        for j:=0; j<n; j++ {
              // 若 i = 0 且 j =0,则示意以后地位为起始地位,不存在左方、上方节点
            if i == 0 && j == 0 {min = 0} else {
                if i == 0 { // i= 0 示意第 0 行,不存在上方节点,则最小值从以后地位的左方失去
                   min = minPath[i][j-1] 
                } else if j == 0 { // j= 0 示意示意第 0 列,不存在左方节点,则最小值从以后地位的上方失去
                    min = minPath[i-1][j]
                } else if minPath[i-1][j] > minPath[i][j-1] { // 当左方、上方节点值存在时,取最小值
                    min = minPath[i][j-1]
                } else {min = minPath[i-1][j]
                }
            }

            minPath[i][j] = min + grid[i][j]
        }
    }

    return minPath[m-1][n-1]
}

结语

​ 动静布局在生活中的利用极其宽泛,包含工程技术、经济、工业生产、军事以及自动化管制等畛域,并在背包问题、生产经营问题、资金治理问题、资源分配问题、最短门路问题和简单系统可靠性问题等中获得了显著的成果。

​ 本篇文章,旨在帮忙大家对动静布局有个根本的理解,拓宽大家解决问题的思路,当然对动静布局感兴趣的小伙伴还能够持续找找相干题目,晋升对它的了解。

退出移动版