Definition(DP):
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a modest expenditure in storage space.

母牛问题：
初始时间只有一头母牛，第二年开始每只成熟的母牛都会产下一头小母牛，一头小母牛话费3年成熟且可以再生下小母牛；求解第n年总母牛头数。
S(n) = S(n - 1) + S(n - 3)
S(1) = 1
S(2) = 2
S(3) = 3

Fibonacci数列问题：
从第三项开始每一项等于前两项的和。
S(n) = S(n - 1) + S(n - 2)
S(1) = 1
S(2) = 1

以上两个问题均可以用递归和根据公式用循环的方法来计算，时间复杂度分别为2^n和n, 以斐波那契额问题为例，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//java version
//recursive

public static int getFibnacciRecurse(int n){
    if(n < 1){
        return 0;
    }else if(n == 1 || n == 2){
        return 1;
    }
    
    return getFibonacciRecurse(n - 1) + getFibonacciRecurse(n - 2);
}

//java version
//loop
public static int getFibonacciLoop(int n){
    
    int m1 = 1, m2 = 1;
    int index = 3, tmp = 0;
    
    while(index <= n){
        tmp = m1 + m2;
        m1 = m2;
        m2 = tmp;
        index++;
    }
    
    return tmp;
}

利用矩阵计算方法，为了更快的计算
考虑到A(n) = A(n - 1) + A(n - 2), 右侧可以写成矩阵相乘的形式：

对上式可以进一步变形，成：

重复使用此公式，可以得到：

计算结果，快速幂计算方法：首先考虑计算10^15，15二进制为00001111，当计算10^1之后其结果可以用来计算10^2，因此10^4，10^8也可以通过一次乘法计算出来；通过这种方式可以在log(n)的时间复杂度上计算出矩阵的幂。
以下为快速矩阵方式计算斐波那契额数列第n项代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//java version
//quick matrix multi of pow exp
public static long[][] MatrixPowerSpeed(long[][] matrix, int pow){
		
		long[][] tmp = matrix;
		long[][] res = new long[matrix.length][matrix[0].length];
		
		for(int i = 0; i < matrix.length; i ++){
			res[i][i] = 1;
		}
		
		while(pow != 0){
			
			if ((pow & 1) != 0) {
				res = Matrix.MatrixMulti(res, tmp);
			}
			
			tmp = Matrix.MatrixMulti(tmp, tmp);
			pow = pow >> 1;
		}
		
		return res;
	}

//basic two matrix multi
public static long[][] MatrixMulti(long[][] matrix1, long[][] matrix2){
		
		int matrix1RowLen = matrix1.length;
		int matrix1ColumnLen = matrix1[0].length;
		int matrix2RowLen = matrix2.length;
		int matrix2ColumnLen = matrix2[0].length;
		
		if (matrix1ColumnLen != matrix2RowLen) {
			System.out.println("matrix multi condition not met!");
		}
		
		long[][] res = new long[matrix1RowLen][matrix2ColumnLen];
		
		for(int i = 0; i < matrix1RowLen; i++){
			for(int j = 0; j < matrix2ColumnLen; j++){
				res[i][j] = 0;
				for(int k = 0; k < matrix1ColumnLen; k ++){
					res[i][j] += matrix1[i][k] * matrix2[k][j];
				}
			}
		}
		
		return res;
}

###How to write simple deadloop, check following.

while(true){}

.section        __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 13
.globl  _main                   ## -- Begin function main
.p2align        4, 0x90

_main: ## @main
.cfi_startproc

BB#0:

pushq   %rbp

Lcfi0:
.cfi_def_cfa_offset 16
Lcfi1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Lcfi2:
.cfi_def_cfa_register %rbp
movl $0, -4(%rbp)
LBB0_1: ## =>This Inner Loop Header: Depth=1
jmp LBB0_1
.cfi_endproc

## -- End function

As we can see, there is no condition judgement after LBB0_1. Now check this,

LBB0_1: ## =>This Inner Loop Header: Depth=1
xorl %eax, %eax
movb %al, %cl
testb $1, %cl
jne LBB0_2
jmp LBB0_3
LBB0_2: ## in Loop: Header=BB0_1 Depth=1
jmp LBB0_1
LBB0_3:
xorl %eax, %eax
popq %rbp
retq
.cfi_endproc
LBB0_2 is used to execute next loop, if exit condition meets, jmp LBB0_3 will be executed.

for(;;){}

int main(){

for(int i = 0; i < 10; i++){
    i += 2;
}
return 0;

}

.section        __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 13
.globl  _main                   ## -- Begin function main
.p2align        4, 0x90

_main: ## @main
.cfi_startproc

BB#0:

pushq   %rbp

Lcfi0:
.cfi_def_cfa_offset 16
Lcfi1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Lcfi2:
.cfi_def_cfa_register %rbp
movl $0, -4(%rbp)
movl $0, -8(%rbp)
LBB0_1: ## =>This Inner Loop Header: Depth=1
cmpl $10, -8(%rbp)
jge LBB0_4

BB#2: ## in Loop: Header=BB0_1 Depth=1

movl    -8(%rbp), %eax
addl    $2, %eax
movl    %eax, -8(%rbp)

BB#3: ## in Loop: Header=BB0_1 Depth=1

movl    -8(%rbp), %eax
addl    $1, %eax
movl    %eax, -8(%rbp)
jmp     LBB0_1

LBB0_4:
xorl %eax, %eax
popq %rbp
retq
.cfi_endproc

## -- End function

Firstly, i is initialized with 0, then condition judgement is executed in LBB0_1, if condition meets, goto LBB0_4, else BB#2 and BB#3 will be executed.

As wrote before, if condition judgement is not provided, the next step is jmp exit.

label
This is the most basic ways with label, which is common in ASM.

0.1.2.?2. quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
  input: 
          arr:  array for type int *
          low:  index of first element in array
          high: index of last element in arrray
  output:
          arr
  return:
          the last pivotkey index
  prerequisites:
          none 
*/
int partition(int arr[], int low, int high){

    int pivotkey = arr[low];
    int index = 0;
    int temp = 0;

    while(low < high){
        while(low < high && arr[high] >= pivotkey) high--;
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;

        while(low < high && arr[low] <= pivotkey) low++;
        temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }
    arr[low] = pivotkey;

    for(index = 0; index <= 5; index++){
        printf("%d\t", arr[index]);
    }
    printf("\n");
    return low;
}

void qsort(int arr[], int low, int high){

    if(low < high){
        int retIndex = partition(arr, low, high);
        qsort(arr, low, retIndex - 1);
        qsort(arr, retIndex + 1, high);
    }
}