动静布局

引子 - 爬楼梯

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

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阶为例

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

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

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

注释 - 动静布局

1.概念

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

2.DP能够解决的问题

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

最优子结构：一个最优化策略的子策略总是最优的。
无后效性：问题的历史状态不影响将来的倒退；只能通过以后的状态影响将来；以后的状态是对以往历史的总结

3.用DP解决问题的思路

状态定义：形容第 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]}

结语

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

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