leedcode 动态规划

链接

动态规划即将问题降阶为小问题并且利用当前规模问题的信息和比之更小的问题的解进行求解当前规模问题。

爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

题目解析

设c[n]为n节楼梯的可能总数。则 c[n]=c[n-1]+c[m-2]; 即从上一节上一节，从上两节上两节。但是不可以从上两节上两次一节，因为这样的话就与 c[n-1] 重复了。

代码

int climbStairs(int n)
{
    // c[n]=c[n-1]+c[n-2]*2;
    //int *c=(int *)malloc(n*sizeof(int));
    int c[100]={0};
    c[1]=1;
    c[2]=2;
    for(int i=3;i<=n;i++)
        c[i]=c[i-1]+c[i-2];
    return c[n];
}

买卖股票的最佳时机

问题描述

给你一个序列代表股票，每天的价钱，选择一天进行购买并在之后的某一天卖出。求你可以挣得最大值。

问题分析

这个问题当然可以使用暴力进行求解。遍历每一天进行买入并遍历之后的每一天进行卖出。从而得到最大值。

但是暴力求解显然太low了。问题的关键在于如何找到两天 i j 使得 j-i 最大。如果每一天都知道其前面的那些天中股票的最小值的话不就可以知道在这一天买入可以赚的钱了吗。所以维护维护一个数组dp[n],代表截至到今天股票的最低价格。显然 dp[n]=min(dp[n-1],price[n]) 然后就可以算出今天卖出的最大收益。便利数组即可得到最大收益。

代码

int maxProfit(int* prices, int pricesSize)
{
    int n=pricesSize;
    int *dp=(int *)malloc(n*sizeof(int));
    *(dp)=*(prices);
    int max=0;
    for(int i=1;i<=n-1;i++)
    {
        *(dp+i)=*(dp+i-1)<*(prices+i)?*(dp+i-1):*(prices+i);
        if(*(prices+i)-*(dp+i)>max)
            max=*(prices+i)-*(dp+i);
    }
    return max;
}

观察代码可知需要保存的数据其实只有dp[i-1]而已，所以可以进行简化。

int maxProfit(int *prices, int pricesSize)
{
    int dp = *prices;
    int max = 0;
    int i = 0;
    while (++i <= pricesSize - 1)
    {
        dp = dp < *(prices + i) ? dp : *(prices + i);
        max = *(prices + i) - dp > max ? *(prices + i) - dp : max;
    }
    return max;
}

最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

题目解析 方法一

和上面那一道买卖股票一样的思想。遍历得到每一个从0开始到当前前一个数的和。然后 s[n]-min+nums[n]即为以当前元素为末尾的最大元素和。不过这种思想的代码要考虑的情况比较多。

int maxSubArray(int *nums, int numsSize)
{
    if(numsSize==1)
        return *nums;
    // dp[n]
    //便利一次得到 s[i] 为前 i-1个元素之和 
    //然后像买股票一样 得到最大的 s[m]-s[n]+nums[m] 即为最大的子序列和
    int *s = (int *)malloc((numsSize+1) * sizeof(int));
    int *num=(int *)realloc(nums,(numsSize+1) * sizeof(int));
    *(num+numsSize)=(*(num+numsSize-1)<0)?*(num+numsSize-1):0;
    *s=0;
    int max=*num;
    int min=0;
    for(int i=1;i<=numsSize;i++)
    {
        *(s+i)=*(s+i-1)+*(num+i-1); //s[n] = sum of first i-1 ele
        min=*(s+i)<min?*(s+i):min;
        int a=*(s+i)+*(num+i)-min;
        max=a>max?a:max;
    }
    return max;
}

题目解析 方法二

设当前虽大和为 s[i] 则 s[i]=max{s[i-1]+nums[i],nums[i]} 也就是说 s[i]=s[i-1]>0?s[i-1]+nums[i]:nums[i]; max=max{max,s[i]};

int maxSubArray(int *nums, int numsSize)
{
    int s=*nums;
    int max=s;
    for(int i=1;i<=numsSize-1;i++)
    {
        s=s<0?*(nums+i):s+*(nums+i);
        max=s>max?s:max;
    }
    return max;
}

打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

题目解析

动态规划首先要明确大规模问题如何转化为小规模的问题。由此进行从小到大的递推。

设 dp[n] 代表偷前n家可以达到的最大钱数。 则分为两种情况：

1. 偷 n 则不能偷 n-1 所以 dp[n]=dp[n-2]+nums[n];
2. 不偷 n 则可以偷 n-1 dp[n]=dp[n-1];

这里有一个疑问，就是如果不偷n时，如果恰好在判断是否偷 n-1 时也得出不偷 n-1 的话，岂不是dp[n]不是最大值（少了一个nums[n])，我们再来演示一下：

1. 若 n-1 没有偷，则 dp[n-1]=dp[n-2]
2. 此时 对于 n 来讲 dp[n]=max{nums[n]+dp[n-2],dp[n-1]} 由于dp[n-2]==dp[n-1] 则一定 nums[n]+dp[n-2]>dp[n-1] 即一定偷n。

代码

int rob(int *nums, int numsSize)
{
    if(numsSize==1)
        return *nums;
    if(numsSize==2)
        return *(nums)>*(nums+1)?*(nums):*(nums+1);
    int *dp=(int *)malloc(numsSize*sizeof(int));
    *dp=*nums;
    *(dp+1)=*(nums)>*(nums+1)?*(nums):*(nums+1);
    for(int i=2;i<=numsSize-1;i++)
    {
        *(dp+i)=*(dp+i-2)+*(nums+i)>*(dp+i-1)?*(dp+i-2)+*(nums+i):*(dp+i-1);
    }
    return *(dp+numsSize-1);
}