乐趣区

关于算法:动态规划

jiezi

动静布局

引子 – 爬楼梯

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

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] 为在第 i 行j列时的最小门路和

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]
}

结语

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

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

退出移动版