【1】动态规划
文章目录
一直以为动态规划是一种具体算法。其实动态规划是一种思想。
“记住求过的解来节省时间”。
一个典型的例子是斐波那契数列,
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;
}使用一个数组来保存中间数据,最后得到答案。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论