关于算法:动态规划

始终认为动静布局是一种具体算法。其实动静布局是一种思维。
“记住求过的解来节省时间”。
一个典型的例子是斐波那契数列，

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

其中的递归会将雷同的数字计算屡次，造成程序的低效。

改良int fibonacci(int n){    int i=0, last =0, next_to_last =0, answer =0;    if(n<=1)        return 1;     last = next_to_last =1;     for (i=2; i<=n; i++)     {        answer = last+next_to_last;        next_to_last = last;        last = answer;     }     return answer;}

另外一个是LeetCode 198题，打家劫舍

#define max(a,b) ((a>b)?(a):(b))int rob(int* nums, int numsSize){    //dp[i] = max(dp[i-2]+k,dp[i-1]);    int ret =0;    if(numsSize ==0)        return 0;    if(numsSize ==1)        return nums[0];    if(numsSize ==2)        return max(nums[0],nums[1]);    int i=0;    int * dp = ( int* )malloc( sizeof(int) * (numsSize+1));    dp[0] = nums[0];    dp[1] = max(nums[0],nums[1]);    for (i=2; i<numsSize; i++)    {        if(dp[i-2]+nums[i] >= dp[i-1])        {            dp[i] = dp[i-2] + nums[i];        }        else        {            dp[i] = dp[i-1];        }    }    ret = dp[numsSize-1];    free(dp);    return ret;}

应用一个数组来保留两头数据，最初失去答案。