关于算法:动态规划

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

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

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