前言

最近在牛客网上做了几套公司的真题，发现有关动态规划（Dynamic Programming）算法的题目很多。相对于我来说，算法里面遇到的问题里面感觉最难的也就是动态规划（Dynamic Programming）算法了，于是花了好长时间，查找了相关的文献和资料准备彻底的理解动态规划（Dynamic Programming）算法。一是帮助自己总结知识点，二是也能够帮助他人更好的理解这个算法。后面的参考文献只是我看到的文献的一部分。



动态规划算法的核心

理解一个算法就要理解一个算法的核心，动态规划算法的核心是下面的一张图片和一个小故事。





A * "1+1+1+1+1+1+1+1 =？" *

A : "上面等式的值是多少"
B : *计算* "8!"

A *在上面等式的左边写上 "1+" *
A : "此时等式的值为多少"
B : *quickly* "9!"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

由上面的图片和小故事可以知道动态规划算法的核心就是记住已经解决过的子问题的解。



动态规划算法的两种形式

上面已经知道动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：①自顶向下的备忘录法  ②自底向上。 

为了说明动态规划的这两种方法，举一个最简单的例子：求斐波拉契数列Fibonacci 。先看一下这个问题：



Fibonacci (n) = 1;   n = 0

Fibonacci (n) = 1;   n = 1

Fibonacci (n) = Fibonacci(n-1) + Fibonacci(n-2)

以前学c语言的时候写过这个算法使用递归十分的简单。先使用递归版本来实现这个算法：



public int fib(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return fib( n-1)+fib(n-2);
}
//输入6
//输出：8


先来分析一下递归算法的执行流程，假如输入6，那么执行的递归树如下：



上面的递归树中的每一个子节点都会执行一次，很多重复的节点被执行，fib(2)被重复执行了5次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。下面就看看动态规划的两种方法怎样来解决斐波拉契数列Fibonacci 数列问题。



①自顶向下的备忘录法



public static int Fibonacci(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];        
        for(int i=0;i<=n;i++)
            Memo[i]=-1;
        return fib(n, Memo);
    }
    public static int fib(int n,int []Memo)
    {

        if(Memo[n]!=-1)
            return Memo[n];
    //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。               
        if(n<=2)
            Memo[n]=1;

        else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  

        return Memo[n];
    }

备忘录法也是比较好理解的，创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib（n）的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在Memo数组中，下次在调用fib（n）的时候就不会重新递归了。比如上面的递归树中在计算fib（6）的时候先计算fib（5），调用fib（5）算出了fib（4）后，fib（6）再调用fib（4）就不会在递归fib（4）的子树了，因为fib（4）的值已经保存在Memo[4]中。



②自底向上的动态规划

备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）……,那么何不先计算出fib（1），fib（2），fib（3）……,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。



public static int fib(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for(int i=2;i<=n;i++)
        {
            Memo[i]=Memo[i-1]+Memo[i-2];
        }       
        return Memo[n];
}

自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。观察参与循环的只有 i，i-1 , i-2三项，因此该方法的空间可以进一步的压缩如下。



public static int fib(int n)
    {
        if(n<=1)
            return n;

        int Memo_i_2=0;
        int Memo_i_1=1;
        int Memo_i=1;
        for(int i=2;i<=n;i++)
        {
            Memo_i=Memo_i_2+Memo_i_1;
            Memo_i_2=Memo_i_1;
            Memo_i_1=Memo_i;
        }       
        return Memo_i;
    }

一般来说由于备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。 

你以为看懂了上面的例子就懂得了动态规划吗？那就too young too simple了。动态规划远远不止如此简单，下面先给出一个例子看看能否独立完成。然后再对动态规划的其他特性进行分析。



动态规划小试牛刀

例题：钢条切割







上面的例题来自于算法导论 

关于题目的讲解就直接截图算法导论书上了这里就不展开讲。现在使用一下前面讲到三种方法来来实现一下。 
①递归版本



public static int cut(int []p,int n)
    {
        if(n==0)
            return 0;
        int q=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++)
        {
            q=Math.max(q, p[i-1]+cut(p, n-i));  
        }
        return q;
    }

递归很好理解，如果不懂可以看上面的讲解，递归的思路其实和回溯法是一样的，遍历所有解空间但这里和上面斐波拉契数列的不同之处在于，在每一层上都进行了一次最优解的选择，q=Math.max(q, p[i-1]+cut(p, n-i));这个段语句就是最优解选择，这里上一层的最优解与下一层的最优解相关。

②备忘录版本



public static int cutMemo(int []p)
    {
        int []r=new int[p.length+1];
        for(int i=0;i<=p.length;i++)
            r[i]=-1;                        
        return cut(p, p.length, r);
    }
    public static int cut(int []p,int n,int []r)
    {
        int q=-1;
        if(r[n]>=0)
            return r[n];
        if(n==0)
            q=0;
        else {
            for(int i=1;i<=n;i++)
                q=Math.max(q, cut(p, n-i,r)+p[i-1]);
        }
        r[n]=q;

        return q;
    }

有了上面求斐波拉契数列的基础，理解备忘录方法也就不难了。备忘录方法无非是在递归的时候记录下已经调用过的子函数的值。这道钢条切割问题的经典之处在于自底向上的动态规划问题的处理，理解了这个也就理解了动态规划的精髓。

③自底向上的动态规划



public static int buttom_up_cut(int []p)
    {
        int []r=new int[p.length+1];
        for(int i=1;i<=p.length;i++)
        {
            int q=-1;
            //①
            for(int j=1;j<=i;j++)
                q=Math.max(q, p[j-1]+r[i-j]);
            r[i]=q;
        }
        return r[p.length];
    }

自底向上的动态规划问题中最重要的是理解注释①处的循环，这里外面的循环是求r[1],r[2]……，里面的循环是求出r[1],r[2]……的最优解，也就是说r[i]中保存的是钢条长度为i时划分的最优解，这里面涉及到了最优子结构问题，也就是一个问题取最优解的时候，它的子问题也一定要取得最优解。下面是长度为4的钢条划分的结构图。我就偷懒截了个图。





动态规划原理

虽然已经用动态规划方法解决了上面两个问题，但是大家可能还跟我一样并不知道什么时候要用到动态规划。总结一下上面的斐波拉契数列和钢条切割问题，发现两个问题都涉及到了重叠子问题，和最优子结构。

①最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

②重叠子问题

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。



动态规划的经典模型



线性模型

线性模型的是动态规划中最常用的模型，上文讲到的钢条切割问题就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。【例题1】是一个经典的面试题，我们将它作为线性模型的敲门砖。

【例题1】在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。



每次过桥的时候最多两个人，如果桥这边还有人，那么还得回来一个人（送手电筒），也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次，三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑，将手电筒送回来（也许不是同一个人，realy？！）这个回来的时间是没办法省去的，并且回来的次数也是确定的，为N-2，如果是我，我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话，那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了，花费的总时间：

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19，但是实际答案应该是17。

具体步骤是这样的：

第一步：1和2过去，花费时间2，然后1回来（花费时间1）；

第二歩：3和4过去，花费时间10，然后2回来（花费时间2）；

第三部：1和2过去，花费时间2，总耗时17。

所以之前的贪心想法是不对的。我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i]        (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2]    (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题) 

所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }



区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

【例题2】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。 

典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a’后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：

1、在A[j]后面添加一个字符A[i]；

2、在A[i]前面添加一个字符A[j]；

根据两种决策列出状态转移方程为：

d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1;                (每次状态转移，区间长度增加1)

空间复杂度O(n^2)，时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法。



背包模型

背包问题是动态规划中一个最典型的问题之一。由于网上有非常详尽的背包讲解，这里只将常用部分抽出来。

【例题3】有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，状态转移方程为：

f[i][v] = max{ f[i-1][v], f[i-1][v – Ci] +Wi }

时间复杂度O(VN)，空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V) ）。



动态规划题集整理

1、最长单调子序列 
Constructing Roads In JG Kingdom★★☆☆☆ 
Stock Exchange                                  ★★☆☆☆

2、最大M子段和 
Max Sum ★☆☆☆☆ 
最长公共子串  ★★☆☆☆              

3、线性模型 
Skiing           ★☆☆☆☆



总结

弄懂动态规划问题的基本原理和动态规划问题的几个常见的模型，对于解决大部分的问题已经足够了。希望能对大家有所帮助，转载请标明出处http://write.blog.csdn.net/mdeditor#!postId=75193592，创作实在不容易，这篇博客花了我将近一个星期的时间。



参考文献

1.算法导论

Dynamic Bone插件的Unity Store链接地址：https://assetstore.unity.com/packages/tools/animation/dynamic-bone-16743

 

 

 

Dynamic Bone是一个Unity的动态骨骼插件，这个插件允许开发者指定对应的根骨骼，从而允许该骨骼的子骨骼进行物理结算，而根骨骼将不进行物理结算~~ 有一点要说明哦，DynamicBone模拟的物理结算不会导致骨骼距离发生变化~~也就是说，DynamicBone并不适合模拟凝胶、橡胶等各方向形变明显的物体，这样的物理模型更加适用于模拟头发呀、绳子啊等这些不容易拉伸但容易形变的物体，运用在衣物上时，则需要看衣物材质是否容易拉伸，如果容易拉伸依然不适合用~~

这个插件内含有两个脚本，一个是Dynamic Bone，一个是Dynamic Bone Collider，好了我来一个一个的说明一下

— Dynamic Bone —

Dynamic Bone使用还是比较简单的，导入Package之后，在Unity场景中选中需要计算的带骨骼的GameObject，然后呢，在这个GameObject下面添加DynamicBone组件，然后将最上层的骨骼拖入到DynamicBone组件的Root上即可。然后设置各项参数，DynamicBone就会在物体发生运动的时候自动生效。要注意的是：

注意：因为DynamicBone组件会在启动时会记录所有骨骼的局部坐标并且在每次Update时还原局部坐标，同时会根据所在的GameObject的移动计算骨骼的位置，所以添加DynamicBone组件的 GameObject不能位于应用DynamicBone的模型的骨骼中，就算是根骨骼也不行，如果这样的话，在计算的时候会发生抖动或者直接崩溃~~

 



Dynamic Bone脚本

 

Dynamic Bone有四个基本属性，决定了其运动效果，四个属性的取值范围都是[0, 1]：

 


	
Damping （阻尼）：阻止简谐运动的惯性运动，相当于弹簧的摩擦力。为0时简谐运动过程不会主动停止，为1时简谐运动过程不会发生；
	
	

	
Elasticity （弹性）：决定回振移动强度，在简谐运动过程中作为额外的作用力将节点拉到还原位置，相当于弹簧的弹力。为0时系统形变不会主动还原，为1时形变不会发生；
	
	

	
Stiffness （刚性）：限制最大振动幅度与方向，保证碰撞处理前节点不会跑到指定范围外，相当于弹簧的硬度。为0时不发挥作用，0到1时限制范围从2倍原始距离到0线性衰减；
	
	

	
Inert （惯性）：限制形变幅度，在每一帧的简谐运动迭代发生前，无条件随物体整体运动拉动节点，拉动距离为Inert * 整体运动距离
	
其他的属性说明：


	
Update （更新频率）：DynamicBone计算频率，当游戏实际帧率高于这个更新频率时，DynamicBone会在每一帧进行消极计算，会尽量保持节点形状，但不会进行简谐运动模拟；当DynamicBone更新 频率远远高于游戏帧率的时候，DynamicBone会在脚本执行时尝试追帧，但每次最多执行4次，也就是更新频率实际最高只是当前游戏帧数的4倍；
	
	

	
Radius （半径）：指定每个节点与DynamicBoneCollider发生碰撞的半径，注意节点互相之间不存在碰撞关系，注意这个半径是0碰撞依然会生效；
	
	

	
Damping\Elasticity\Stiffness\Inert\Radius各属性的Distrib：指定属性随着节点深度递增发生的变化；
	
	

	
End Length\End Offset 末尾节点偏移量：指定特殊的末尾节点End Bone局部位置，详见下方的4.1. 关于EndLength和EndOffset；
	
	

	
Gravity 重力：在DynamicBone节点上施加的重力，方向是在全局坐标系中的，注意DynamicBone的重力比较特殊，只在节点运动发生时起效，会在节点运动时把节点向重力方向拉动；
	
	

	
Force 常驻力：在DynamicBone节点上施加的额外力，方向是在全局坐标系中的，注意Force与Gravity不同，是无条件生效的，会一直把节点向指定方向拉动；
	
	

	
Colliders 碰撞体列表：会与DynamicBone各节点发生碰撞的碰撞体对象，详见2.1. 关于碰撞；
	
	

	
Exclusions 排除节点列表：在设置Root节点后，DynamicBone会根据节点的GameObject的父子关系沿着子GameObject方向自动生成节点树，Exclusions中所有节点及其子孙节点都不会 生成DynamicBone节点；
	
	

	
Freeze Axis 固定轴：非None的情况下，所有节点在局部坐标系的对应的轴上在值不会发生变化；
	
	

	
DistanceDisable 距离控制开关：开启或者关闭距离控制机制，开启后如果DynamicBone所在的物体超出了参考物体的参考距离范围，DynamicBone的所有行为都会停止；
	
	

	
Reference Object 参考物体：距离控制机制的参考物体，如果为空则DynamicBone会选择场景内的主摄影机作为参考对象；
	
	

	
Distance To Object 参考距离：距离控制机制的参考距离
	
 

— Dynamic Bone Collider —

DynamicBone提供了简单的碰撞功能，允许使用者禁止进入或者离开某些特定的区域，组件提供了球型和胶囊体两种区域的碰撞体。碰撞功能的使用非常简单，只需要在骨骼可能会发生碰撞交互的GameObject上添加DynamicBoneCollider组件，并且设置以下属性：



Dynamic Bone Collider脚本

 


	
Center：指定区域中心与GameObject位置的偏移量；
	
	

	
Radius：区域内球形部分的半径；
	
	

	
Height：区域高度，这个值在小于2倍Radius时无效，会使区域变成球型，高于2倍Radius时生效，区域会变成胶囊体（可视化模型是两个球体）；
	
	

	
Direction：胶囊体在当前GameObject局部坐标的方向，区域是球体的时候无效；
	
	

	
Bound：区域模式，Outside表示区域会作为碰撞盒与DynamicBone节点发生碰撞，阻止节点进入区域内，而Inside则会约束节点在区域内，阻止节点离开区域； 然后需要将DynamicBoneCollider对象添加至与其发生碰撞交互的DynamicBone组件的Colliders属性中。
	
 

含有DynamicBone的效果

 

好啦~~今天这到这里啦~~记得评论~~点赞~~转发~~~

还有要说明一下：

使用限制和缺陷


	
由于DynamicBone完全不发生拉伸和压缩的特性，DynamicBone并不适合模拟凝胶、橡胶等各方向形变明显的物体，而更适合模拟头发、绳子等不容易拉伸但容易形变的物体， 衣物则要看衣物材质是否容易拉伸，如果容易拉伸依然不适合用DynamicBone模拟；
	
	

	
虽然有简单的碰撞机制，带DynamicBone组件的骨骼之间是不存在碰撞的（当然可以通过在各骨骼都设置DynamicBoneCollider组件来实现，但因为开销会很大所以不建议），所以，这意味着DynamicBone 模拟的物体在刚性为0的时候可能会发生自我穿插；
	
	

	
DynamicBone的位置更新发生在LateUpdate节点，这意味着DynamicBone会完全控制节点的位置，其计算结果会覆盖物理和动画系统输出的位置，而不能与其融合
	

1. 智能指针类型转换用static_pointer_cast，dynamic_pointer_cast等；

2. dynamic_cast/dynamic_pointer_cast的转换，其类族基类中必须至少有一个虚函数，哪怕是虚析构函数。

from:http://realmacsoftware.com/blog/dynamic-linking



dynamic Linking

 Written by Damien on
 April 2nd, 2014 in Engineering

iOS is often criticised for not supporting dynamic libraries. While you might agree or disagree, it is interesting to think about why it is so and how this rule is eventually enforced. In this post we will see
 what these libraries are, how they come in practice, how they would work if they were fully supported on iOS and what makes it impossible to ship one in your iOS application.

Library linking
Applications are very rarely built as one big monolithic executable but are rather constructed by assembling various blocks usually called libraries. From a practical perspective, a library can be thought as an
 agglomerate of executable code along with some public headers and resources conveniently packaged to be linked into and consumed by an application.
While this general definition fits for most library types, there is one area where they diverge: linking. Based on this distinction, there are two families of libraries: static and dynamic libraries. I will quickly
 summarise the differences between the two, however, if you want to know more about the topic, I recommend reading theDynamic
 Library Programming Topics guide on Apple’s website.

Static library
A static library can be thought of as an archive of object files. When linking such a library into an application, the static linker will collect the object files from the library and package
 them along with the application object code into one single executable file. This means that the size of the application executable file will grow with the number of libraries added. Also, when the application launches, the application code (which includes
 the library code) will be loaded all at once into the program’s address space.

Dynamic library
Dynamic libraries allow an application to load code into its address space when it’s actually needed. This can be either at launch time or at runtime. Dynamic libraries are not part of the application executable
 file.
When an application is launched, the application’s code is first loaded into the address space of the process. The dynamic loader – usually dyld on Apple’s platforms
 – takes control of the process and loads the dependent libraries. This involves resolving their location on the file system based on their install name, and then resolving the undefined external symbols needed by the application. The dynamic
 loader will also load additional libraries at runtime, as they are requested.

Framework
In the Apple world, a Framework is a bundle or package containing a dynamic library, header files and resources. Frameworks are a very neat way to group related resources together, provide an executable along
 with the public headers in one package that is easy to install.
It is important to note that while a framework would need to contain a dynamic library, one could quite easily create a static framework for iOS. I won’t go into details about this here but I highly recommend
 reading “iPhone Framework Support - Shipping Libraries” and “iOS
 Static Libraries Are, Like, Really Bad, And Stuff” by Landon Fuller.

Dynamic libraries on iOS
So, is it true that dynamic libraries cannot be used on iOS? Well, it is actually a bit of a misconception. Every Apple framework that you link into your application contains a dynamic shared library. Can you
 imagine what the size of the executable would be if you had to statically link UIKit and other frameworks into every single application?

As a matter of fact, dynamic libraries are wildly used on iOS. When your code inapplicationDidFinishLaunching: starts
 executing, dyld has already loaded over 150 libraries!
It would be neat if we could find out which libraries are being loaded while the application is running. Luckily dyld offers some hooks for an application to be notified when an image is
 added or removed. Let’s create a LLImageLogger class and set some callback functions when
 the class loads. Let’s go through the implementation of this class. You can find the code on GitHub if you want to run it; it comes with a couple of iOS and OS X
 sample applications.

Logging loaded dynamic libraries
mach-o/dyld.h declares two very useful functions:_dyld_register_func_for_add_image and_dyld_register_func_for_remove_image.
 These functions are documented as follows:
The following functions allow you to install callbacks which will be called by dyld whenever an image is loaded or unloaded.
During a call to `_dyld_register_func_for_add_image()` the callback func is called for every existing image. Later, it is called as each new image is loaded and bound (but initializers not yet run).
The callback registered with `_dyld_register_func_for_remove_image()` is called after any terminators in an image are run and before the image is un-memory-mapped.
We can easily add a couple of callbacks when our class loads.
#import <mach-o/dyld.h>

@implementation LLImageLogger

+ (void)load
{
    _dyld_register_func_for_add_image(&image_added);
    _dyld_register_func_for_remove_image(&image_removed);
}
@end
We now need to implement both functions. Note that the signature of the callback function is as follows:
void callback_function(const struct mach_header *mh, intptr_t vmaddr_slide);
Ideally, we will want to log some info about the loaded image to the console. The most familiar way will be to try and mimic the format of a crash report. A crash report usually has a list of images that were
 loaded when the program crashed. The information for each image contains the executable path, the base address, the executable text section size (or the end address) and the image UUID. These informations are very useful when it comes to symbolicate a crash
 report.
0x2fd23000 - 0x2ff0dfff Foundation armv7s  <b75ca4f9d9b739ef9b16e482db277849> /System/Library/Frameworks/Foundation.framework/Foundation

0x31c2c000 - 0x3239ffff UIKit armv7s  <f725ad0982673286911bff834295ec99> /System/Library/Frameworks/UIKit.framework/UIKit
Since the callback functions are passed a pointer to the Mach-O header as first argument it should be fairly easy to retrieve this info. Let’s implement both callback functions and simply call into a common function
 with an extra argument determining whether the image was added or removed.
#import <mach-o/loader.h>

static void image_added(const struct mach_header *mh, intptr_t slide)
{
    _print_image(mh, true);
}

static void image_removed(const struct mach_header *mh, intptr_t slide)
{
    _print_image(mh, false);
}
We will now look at implementing the _print_image function.
 Most of the info about the Mach-O header can be retrieved by means of a function defined indlfcn.h: dladdr.
 By passing the pointer to the Mach-O header and a reference to a Dl_info struct we can
 retrieve some key information about the image. TheDl_info struct contains the following
 members:
typedef struct dl_info {
    const char  *dli_fname;     /* Pathname of shared object */
    void        *dli_fbase;     /* Base address of shared object */
    const char  *dli_sname;     /* Name of nearest symbol */
    void        *dli_saddr;     /* Address of nearest symbol */
} Dl_info;
Keeping this in mind, we can now take a look at the implementation of the_print_image function:
#import <dlfcn.h>

static void _print_image(const struct mach_header *mh, bool added)
{
    Dl_info image_info;
    int result = dladdr(mh, &image_info);

    if (result == 0) {
        printf("Could not print info for mach_header: %p\n\n", mh);
        return;
    }

    const char *image_name = image_info.dli_fname;

    const intptr_t image_base_address = (intptr_t)image_info.dli_fbase;
    const uint64_t image_text_size = _image_text_segment_size(mh);

    char image_uuid[37];
    const uuid_t *image_uuid_bytes = _image_retrieve_uuid(mh);
    uuid_unparse(*image_uuid_bytes, image_uuid);

    const char *log = added ? "Added" : "Removed";
    printf("%s: 0x%02lx (0x%02llx) %s <%s>\n\n", log, image_base_address, image_text_size, image_name, image_uuid);
}
As you can see, it’s nothing too fancy. We start by retrieving the Dl_info struct
 for the Mach-O header and then populate the required information. While the base address and image path are directly available in the struct, we will have to manually retrieve the image text segment size and the image UUID from the binary. This is exactly
 what the _image_retrieve_uuid and _image_text_segment_size do.
For these two functions, we will have to walk the Mach-O file load commands. I recommend reading the OS
 X ABI Mach-O File Format Reference from Apple for a good overview of the Mach-O file format. In a nutshell, a Mach-O file is composed of a header, a series of load commands and data composed of multiple segments. Information about the segments (such as
 their offset and size) is available in the segment load commands.
We will start with creating a visitor function that we’ll be able to reuse across both functions.
static uint32_t _image_header_size(const struct mach_header *mh)
{
    bool is_header_64_bit = (mh->magic == MH_MAGIC_64 || mh->magic == MH_CIGAM_64);
    return (is_header_64_bit ? sizeof(struct mach_header_64) : sizeof(struct mach_header));
}

static void _image_visit_load_commands(const struct mach_header *mh, void (^visitor)(struct load_command *lc, bool *stop))
{
    assert(visitor != NULL);

    uintptr_t lc_cursor = (uintptr_t)mh + _image_header_size(mh);

    for (uint32_t idx = 0; idx < mh->ncmds; idx++) {
        struct load_command *lc = (struct load_command *)lc_cursor;

        bool stop = false;
        visitor(lc, &stop);

        if (stop) {
            return;
        }

        lc_cursor += lc->cmdsize;
    }
}
This functions takes a pointer to a Mach-O header and a visitor block. It then invokes the block for each load command it finds. Note the helper function to retrieve the size of the Mach-O header which we’ll need
 in order to find the address of the first load command. This is due to the fact that there are two different structs for the Mach-O header: mach_header and mach_header_64,
 based on whether the architecture is 64-bit or not. Luckily the first field in the header struct is a magic number giving information about the architecture.
With this helper function written we should be able to implement the_image_retrieve_uuid and _image_text_segment_size functions.
static const uuid_t *_image_retrieve_uuid(const struct mach_header *mh)
{
    __block const struct uuid_command *uuid_cmd = NULL;

    _image_visit_load_commands(mh, ^ (struct load_command *lc, bool *stop) {
        if (lc->cmdsize == 0) {
            return;
        }
        if (lc->cmd == LC_UUID) {
            uuid_cmd = (const struct uuid_command *)lc;
            *stop = true;
        }
    });

    if (uuid_cmd == NULL) {
        return NULL;
    }

    return &uuid_cmd->uuid;
}
This function is very simple too. It looks for the LC_UUID command
 and retrieves the uuid_t once it finds it. The _print_image will
 then take care of transforming the uuid_t into a string by mean of uuid_unparse.
Finally, here is the implementation of the _image_text_segment_size function:
static uint64_t _image_text_segment_size(const struct mach_header *mh)
{
    static const char *text_segment_name = "__TEXT";

    __block uint64_t text_size = 0;

    _image_visit_load_commands(mh, ^ (struct load_command *lc, bool *stop) {
        if (lc->cmdsize == 0) {
            return;
        }
        if (lc->cmd == LC_SEGMENT) {
            struct segment_command *seg_cmd = (struct segment_command *)lc;
            if (strcmp(seg_cmd->segname, text_segment_name) == 0) {
                text_size = seg_cmd->vmsize;
                *stop = true;
                return;
            }
        }
        if (lc->cmd == LC_SEGMENT_64) {
            struct segment_command_64 *seg_cmd = (struct segment_command_64 *)lc;
            if (strcmp(seg_cmd->segname, text_segment_name) == 0) {
                text_size = seg_cmd->vmsize;
                *stop = true;
                return;
            }
        }
    });

    return text_size;
}
Nothing too fancy here either. The visitor block simply looks for segment commands (LC_SEGMENT on
 32-bit and LC_SEGMENT_64 on 64-bit) and checks whether the current load segment is the __TEXT segment.
 If it is, it then retrieves the vmsizeand returns it as the text size.
By running the application on the iOS Simulator, the following is logged:
Added: 0x10000b000 (0x2a8000) /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator7.1.sdk/System/Library/Frameworks/Foundation.framework/Foundation <C299A741-488A-3656-A410-A7BE59926B13>
…
Added: 0x110527000 (0x385000) /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator7.1.sdk/System/Library/Frameworks/AudioToolbox.framework/AudioToolbox <57B61C9C-8767-3B3A-BBB5-8768A682383A>
There are 147 images loaded when launching a very simple iOS application!
We thus showed that dynamic libraries were indeed loaded in our iOS application. So what about the dynamic
 libraries are not supported on iOS argument? Well, let’s try and build one and see what happens!

Building a dynamic library on iOS
In the following section, we will attempt to build three products that are common on the Mac but not supported on iOS:
A simple dynamic library linked by the application
A framework (a legit one, containing a dynamic shared library)
A plugin (i.e. a bundle containing an executable, not packaged with the application but loaded at runtime)
As usual, you can find the sample project on GitHub.

Dynamic library on iOS
Let’s start by creating a dynamic library target for our iOS application. Oh wait…
Xcode (logically) doesn’t provide a configuration template for a dynamic library on iOS. Luckily we can select a library from the OS X section and simply change the deployment target and architectures to build
 in the Build Settings.
If you do this and create your library however, you will get an error when trying to build
Check dependencies:

Target specifies product type 'com.apple.product-type.library.dynamic', but there's no such product type for the 'iphoneos' platform
In order to fix this you will have to update the Xcode Specifications for the PackageTypes and ProductTypes for both the iPhone Simulator and the iPhone OS. Instructions on how to do this can be found here.
With this in mind, we can create a simple class, add a sayHello method
 which implementation simply creates and shows an alert view and add the class to the library target. We can then add the library to the Link
 Binary with Librarybuild phase for the application. Finally we have to add a Copy build phase and copy the dynamic library to the application bundle. See the sample project for more info on how to set this up.
We can then import the library header (we marked it as public and made sure that it was in the Header Search Paths), instantiate an object and call the sayHellomethod.
 If you run the application in the iOS simulator you should see the alert view popping up. Wait, did we just load and run some code from a dynamic library and iOS? Looks like it… (Don’t attempt to run this on a device just yet, we’ll discuss it later).

Framework on iOS
Now that we‘ve seen that we can load and use a dynamic library, it would be awesome if we could just build a framework around it so that we can pack additional resource easily and don’t have to worry about header
 search paths.
Similarly to the dynamic library case we can create a framework by using the Mac template and change the deployment target and build architectures. We will also create a plist that will be copied as a resource
 in the framework bundle. We will load the alert view message from the plist, mostly to demonstrate that resource loading works fine from the framework bundle.
Making sure that the header has been marked as public, we can then simply import the framework in the application:
#import "Framework/Framework.h"
Finally, we can instantiate the class and call the method. We should see the alert which message has been loaded from a resource in the framework bundle. It works!

Plugin on iOS
This last one is the most interesting. Applications on the Mac can be extended in a very neat way by supporting plugins. In simple words, a plugin, just like a framework, is a bundle containing an executable and
 some resources. The plugin declares its principal class in its Info.plist. Usually the
 principal class is a subclass of an abstract class defined by the application or conforms to a protocol made available by the application.
In order to load the plugin at runtime, the host application will instantiate anNSBundle instance
 for the plugin location, preflight the bundle to check that it can indeed be loaded and eventually load it. Loading a bundle will dynamically loads the bundle’s executable code into the running program. Once the bundle has been loaded the host application
 can retrieve the principal class and instantiate it.
So let’s try and build this for iOS. We can create a new target by using the Bundle template. After changing the deployment target and build architecture we create a new class and set it as the NSPrincipalClass in
 the Info.plist. Similarly to the framework we will create a plist and load the alert message
 from it at runtime. We also need to make sure that we specify a custom extension for the bundle – here we will use llplugin.
We can then build the plugin and keep the product somewhere safe. We will then copy it in the Documents directory of the iOS application (you can find the application under ~/Library/Application
 Support/iPhone Simulator/7.1-64/Applications. You might have to change the SDK version based on your platform)
In the host application, we will need to add an imported UTI for the plugin so that we can recognize its file type.
With the plugin type declared we can now iterate through the contents of the Documents directory and look for plugins, checking conformance to the type for every found item by using UTTypeConformsTo.
 For each found plugin we can then load the bundle, retrieve the principal class and instantiate it.
- (void)_loadPluginAtLocation:(NSURL *)pluginLocation
{
    NSBundle *plugin = [[NSBundle alloc] initWithURL:pluginLocation];

    NSError *preflightError = nil;
    BOOL preflight = [plugin preflightAndReturnError:&preflightError];
    if (!preflight) {
        return;
    }

    BOOL loaded = [plugin load];
    if (!loaded) {
        return;
    }

    Class pluginClass = [plugin principalClass];
    if (pluginClass == nil) {
        return;
    }

    id pluginInstance = [[pluginClass alloc] init];
    if (![pluginInstance respondsToSelector:@selector(sayHello)]) {
        return;
    }

    [pluginInstance sayHello];
}
If we copy our built plugin in the Documents directory and run the application we should see an alert saying hello. By using the LLImageLogger we
 can also note that the LLPlugin image is only loaded by the time -[NSBundle
 load] is called.
We were able to link and load a dynamic library and a framework in an iOS application running in the simulator. We were also able to dynamically load a plugin at runtime and run some of its code, also in the simulator.
 As you might have guessed there is a catch. So far we’ve only been running our application in the simulator. What happens if we run it on a device?

What about running on the device?
If you attempt to build for running on an actual device Xcode will likely complain that the libraries need to be codesigned. Even if you codesign them you will run into problems when launching your application
 (this might not happened while you’re debugging the application due to the fact that applications behave slightly differently while being debugged on a device on which Developer Mode has been enabled).

Linked dynamic library
When attempting to run the application containing the dynamic library on the device Xcode will prompt you that the dynamic library has to be code signed. We can simply sign it using the same code sign identity
 as the application’s. When running it on the device however you will get the following message during dyld bootstrap and the program will be halted.
dyld: Library not loaded: @executable_path/Library.dylib  
Referenced from: /var/mobile/Applications/DC816A37-F0D4-4F72-9EC8-A642A03C0ABC/Dynamic.app/Dynamic  
Reason: no suitable image found.  
Did find: /var/mobile/Applications/DC816A37-F0D4-4F72-9EC8-A642A03C0ABC/Dynamic.app/Library.dylib: code signature invalid for '/var/mobile/Applications/DC816A37-F0D4-4F72-9EC8-A642A03C0ABC/Dynamic.app/Library.dylib'
So it seems like dyld is denying the load of the library based on the invalidity of its signature.
This happens during the program load, precisely during the dyld bootstrapping. But what about loading a plugin bundle at runtime?

Plugin loaded at runtime
Let’s see what happens when loading our plugin. When attempting to load the plugin at runtime the application will likely crash with the following backtrace:
Exception Type:  EXC_CRASH (SIGKILL - CODESIGNING)

Thread 0 Crashed:
0   dyld 0x2be50c40 ImageLoaderMachO::crashIfInvalidCodeSignature + 72
1   dyld 0x2be5557a ImageLoaderMachOCompressed::instantiateFromFile + 286
2   dyld 0x2be50b44 ImageLoaderMachO::instantiateFromFile + 204
3   dyld 0x2be48036 dyld::loadPhase6 + 390
4   dyld 0x2be4b9b0 dyld::loadPhase5stat + 296
5   dyld 0x2be4b7c6 dyld::loadPhase5 + 390
6   dyld 0x2be4b61c dyld::loadPhase4 + 128
7   dyld 0x2be4b53c dyld::loadPhase3 + 1000
8   dyld 0x2be4afd0 dyld::loadPhase1 + 108
9   dyld 0x2be47e0a dyld::loadPhase0 + 162
10  dyld 0x2be47bb4 dyld::load + 208
11  dyld 0x2be4d1b2 dlopen + 790
12  libdyld.dylib 0x3a09a78a dlopen + 46
13  CoreFoundation 0x2f392754 _CFBundleDlfcnLoadBundle + 120
14  CoreFoundation 0x2f3925a4 _CFBundleLoadExecutableAndReturnError + 328
15  Foundation 0x2fd7f674 -[NSBundle loadAndReturnError:] + 532
16  Foundation 0x2fd8f51e -[NSBundle load] + 18
17  Dynamic 0x000f64be -[LLViewController _loadPluginAtLocation:]
The application is killed while dyld is attempting to load the bundle. We can only see the userland side of things here but the function at the top frame of the stack should give us a good
 idea: ImageLoaderMachO::crashIfInvalidCodeSignature. It is worth noting that the plugin
 we copied into the Documents folder was not code signed. Before attempting to codesign it, let’s quickly analyze what leads to the program being killed when loading the plugin.

In User Space
Luckily, dyld is open-source so we can have a quick look at the implementation of
 the ImageLoaderMachO::crashIfInvalidCodeSignature function to try and figure out what happened.
 The file in question is ImageLoaderMachO.cpp and its implementation is pretty simple:
int ImageLoaderMachO::crashIfInvalidCodeSignature()
{
// Now that segments are mapped in, try reading from first executable segment
// If code signing is enabled the kernel will validate the code signature
// when paging in, and kill the process if invalid
    for (unsigned int i = 0; i < fSegmentsCount; ++i) {
        if ((segFileOffset(i) == 0) && (segFileSize(i) != 0)) {
        // return read value to ensure compiler does not optimize away load
            int* p = (int*)segActualLoadAddress(i);
            return *p;
        }
    }
    return 0;
}
This is a pretty naïve (but effective!) way to check the signature and crash if it’s invalid or inexistent: attempt to read from the first executable segment in the executable letting the kernel kill the process
 should it discover that the code signature cannot be validated when paging in.

In the kernel
The kernel itself is also open-source so we can take a look at it and try and figure out where and how
 the code signature is verified. I should point out here that reading kernel code is slightly out of my confort zone and I found some great help in Charlie Miller’s SyScan’11 talk Don’t
 Hassle The Hoff: Breaking iOS Code Signing and bookiOS Hacker’s Handbook.
While this is a fascinating subject it could get quite lenghty so I won’t go into details here.
In a nutshell, when codesigned, a Mach-O executable will contain aLC_CODE_SIGNATURE load
 command referencing a code signature segment in the binary. We can verify it with otool on a signed binary:
> otool -l Plugin.llplugin/Plugin
…
Load command 17
      cmd LC_CODE_SIGNATURE
  cmdsize 16
  dataoff 9968
 datasize 9616
…
In the kernel, the Mach-O file is loaded and parsed in the parse_machfilefunction
 and the signature is loaded in load_code_signature, both inmach_loader.c.
 Eventually the signature is checked and its validity is stored inside the csflags member
 of the kernel’s proc struct
 for the process.
Later on, whenever a page fault occurs the vm_fault function
 in vm_fault.c is called. During the page fault the signature is validated if necessary. The signature will need to be validated
 if the page is mapped in user space, if the page belongs to a code-signed object, if the page will be writable or simply if it has not previously been validated. Validation happens in the vm_page_validate_cs function
 insidevm_fault.c (the validation process and how it is enforced continually and not only at load time is interesting, see Charlie
 Miller’s book for more details).
If for some reason the page cannot be validated, the kernel checks whether theCS_KILL flag
 has been set and kills the process if necessary. There is a major distinction between iOS and OS X regarding this flag. All iOS processes have this flag set whereas on OS X, although code signing is checked it is not set and thus not enforced.
In our case we can safely assume that the (missing) code signature couldn’t be verified leading to the kernel killing the process.

Situation when code signing the plugin
It was pretty obvious to see that dyld refused to load the plugin executable due to its lack of code signature. We can change this.
codesign --sign "iPhone Developer" --force --verbose=4 Plugin.llplugin
When code signing the plugin bundle by using the codesign Terminal
 utility dyldcorrectly loads the file at runtime and the plugin code executes correctly, even on the device.
We thus have no problem dynamically loading an external plugin bundle containing executable code at runtime, even on a device. There is a big caveat to this: we were able to sign the plugin with our Developer
 certificate given that our device is present in the provisioning profile. For this scenario to happen with a shipped application, the plugin would need to be signed by Apple just like any application submitted to the App Store.
While I don’t see Apple supporting (signed and approved) plugins on iOS anytime soon, I think the dynamic library restrictions could potentially be loosened. By requiring any included executable to be signed with
 the same certificate as the main application – just like for the Mac App Store – Apple could review them as part of the App Store approval process. Dynamic libraries (in particular when bundled in a framework) would make library distribution so much cleaner
 and would obsolete the multitude of hacks we have created in order to simply share code.

Conclusion
Dynamic libraries signed by Apple can be (and are!) loaded by an iOS application
A simple iOS application loads over 150 dynamic libraries on launch
Xcode doesn’t support creating dynamic libraries, frameworks or plugins on iOS but it is very easy to work around this
If code signing were not a thing we could load dynamic libraries, frameworks and load plugins at runtime on iOS just like we do on the Mac
In practice, the kernel will kill any application that attempts to load a dynamic library that is not signed or which signature cannot be validated
A shipping dynamic library would need to be signed by Apple with the same certificate as the one used for App Store applications
Last but not least, the App Store policies don’t allow dynamic libraries and even if it were technically possible it wouldn’t pass App Store validation
You can find the source code for the Image Logger and Dynamic
 iOS projects on GitHub.
扩展：
appstore 审核规则：https://developer.apple.com/app-store/review/guidelines/
lua语言插件话：https://github.com/mmin18/Create-a-More-Flexible-App