[数据结构与算法]动态规划练习(三)

1. 打家劫舍(一)

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

去掉查找最大值的for循环

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

缩减代码

if(numsSize == 2)
        return nums[0]>nums[1]?nums[0]:nums[1];

这块代码是可以看见核心问题的
dp[i] = max(dp[i-1],dp[i-2]+nums[i])

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

2. 打家劫舍(二)

该题与上一题做法相似，只是不能同时选择第一个和最后一个，所以将数组拆分成两个子数字，求最大。

int max(int a,int b){
    return a>b?a:b;
}

int sub_rob(int* nums, int start, int length){
    if(length == 1)
        return nums[start];
    else{
        int i;
        int* dp = (int*)malloc(sizeof(int)*length);
        dp[0] = nums[start];
        dp[1] = max(nums[start],nums[start+1]);
        for(i=2;i<length;i++){
            dp[i] = max(dp[i-1],dp[i-2]+nums[i+start]);
        }
        return dp[length-1];
    }
}


int rob(int* nums, int numsSize){
    if(numsSize == 1)
        return nums[0];
    else if(numsSize == 2)
        return max(nums[0],nums[1]);
    else{
        return max(sub_rob(nums,0,numsSize-1),sub_rob(nums,1,numsSize-1));
    }
}

3. 删除并获得点数

这题与 打家劫舍(二) 相似。

int Max(int a,int b){
    return a>b?a:b;
}

int rob(int* nums, int numsSize){
    if(numsSize == 1)
        return nums[0];
    else{
        int i;
        int* dp = (int*)malloc(sizeof(int)*numsSize);
        dp[0] = nums[0];
        dp[1] = Max(nums[1],nums[0]);
        for(i=2;i<numsSize;i++){
            dp[i] = Max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[numsSize-1];
    }
}

int deleteAndEarn(int* nums, int numsSize){
    int max = nums[0];
    int i = 1;
    while(i<numsSize)
        max = Max(max,nums[i++]);
    int sums[max+1];
    i=0;
    while(i<=max)
        sums[i++] = 0;
    i=0;
    while(i<numsSize){
        sums[nums[i]]+=nums[i];
        i++;
    }
    return rob(sums,max+1);
}