Java教程

算法基础/动态规划1

本文主要是介绍算法基础/动态规划1,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.213. 打家劫舍 II

题目描述:

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。

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

示例:

示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3:
输入:nums = [1,2,3]
输出:3


解答描述:

该题的关键在于:房屋是首尾相连的,而相邻的两个房屋不能同时被偷窃,所以分为两种情况:

1)0号房屋被偷,那么n-1号房屋就不能被偷,则dp范围为0-n-2

2)0号房屋没被偷,那么n-1号房屋就可以被偷,则dp范围为1-n-1。

dp的递推式dp[i]=max(dp[i-2]+nums[i],dp[i-1]),即要么前一个被偷,要么前一个没被偷。

取两种情况的最大值即为最终结果。

注意:当n=0,1,2时,不符合递推式,要特殊判断。

代码:

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0)
        {
            return 0;
        }
        if(n==1)
        {
            return nums[0];
        }
        if(n==2)
        {
            return max(nums[0],nums[1]);
        }
        int *dp=new int[n];
        int max_money=0;
        //因为首尾相连,所以偷了第一号,不能偷第n号,而偷了第n号也不能偷第1号
        //偷第1号 从0-n-1
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        max_money=max(dp[0],dp[1]);
        for(int i=2;i<n-1;i++)
        {
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);//要么前一个被偷了该位置不能再偷,要么前一个没有偷,该位置还能偷
            max_money=max(max_money,dp[i]);
        }
        //没偷第1号 从1-n
        dp[1]=nums[1];
        max_money=max(max_money,dp[1]);
        dp[2]=max(nums[1],nums[2]);
        max_money=max(max_money,dp[2]);
        for(int i=3;i<n;i++)
        {
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
            max_money=max(max_money,dp[i]);
        }
        return max_money;
        
    }
};

2.55. 跳跃游戏

题目描述:

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例:

示例 1:
输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:
输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。


解答描述:

采用贪心策略,用dp[i]表示第i个位置能到达的最远距离,同时用一个变量max_len存储第i个位置前所到达的最远距离。

当max_len比当前位置下标大时,说明当前位置是可达的,那么就可以更新当前位置所能到达的最远距离dp[i]=i+nums[i],并更新max_len,当max_len>=n-1时,说明最后一个下标可到,直接返回true。

代码:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
        {
            return true;
        }
        int *dp=new int[n];//表示当前位置可到达的最远距离
        int max_len=0;
        dp[0]=nums[0];
        max_len=dp[0];
        if(dp[0]>=n-1)
        {
            return true;
        }
        for(int i=1;i<n;i++)
        {
            if(max_len>=i)//如果当前位置可达,那么当前位置能到达额最远距离为i+nums[i]
            {
                dp[i]=i+nums[i];
                max_len=max(max_len,dp[i]);
                if(max_len>=n-1)
                {
                    return true;
                }
            }
            else
            {
                break;
            }
        }
        return false;
    }
};

这篇关于算法基础/动态规划1的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!