【算法刷题 | 动态规划08】6.9（单词拆分、打家劫舍、打家劫舍||）

文章目录

• 21.单词拆分
• • 21.1题目
  • 21.2解法：动规
  • • 21.2.1动规思路
    • 21.2.2代码实现
• 22.打家劫舍
• • 22.1题目
  • 22.2解法：动规
  • • 22.2.1动规思路
    • 22.2.2代码实现
• 23.打家劫舍||
• • 23.1题目
  • 23.2解法：动规
  • • 23.2.1动规思路
    • 23.2.2代码实现

21.单词拆分

21.1题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

• 示例一：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

• 示例二：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词

21.2解法：动规

21.2.1动规思路

21.2.2代码实现

	public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        //先遍历背包
        for(int j=0;j<=s.length();j++){
            //再遍历物品
            for(String word:wordDict){
                int len=word.length();
                if( j>=len && dp[j-len] && word.equals(s.substring(j-len,j))){
                    //若dp[i]为true且[i,j]出现在字典中
                    dp[j]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

22.打家劫舍

22.1题目

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

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

• 示例一：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

• 示例二：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

22.2解法：动规

22.2.1动规思路

1. 确定dp数组以及下标：dp[i]：下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
2. 确定递推公式：偷/不偷：dp[i]=Math.max(nums[i]+dp[i-2]，dp[i-1])
3. dp数组初始化：dp[0]=nums[0]；dp[1]为nums[0]、nums[1]两者的最大者
4. 确定遍历顺序：从前往后

22.2.2代码实现

	public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=nums[0]>nums[1]?nums[0]:nums[1];
        for(int i=2;i<nums.length;i++){
            //取、不取
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[nums.length-1];
    }

23.打家劫舍||

23.1题目

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

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

• 示例一：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

• 示例二：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

23.2解法：动规

23.2.1动规思路

1. 与上一题：打家劫舍不同，该题房屋是呈环状的，即第一个房屋和最后一个房屋是连在一起的

2. 情况一：取第一个房屋：

   

3. 情况二：取最后一个房屋：、

   

23.2.2代码实现

	public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        return Math.max(robRange(nums,0,nums.length-2),robRange(nums,1,nums.length-1));
    }

    //寻找区间[start,end]的最大金额值
    private int robRange(int[] nums,int start,int end){
        if(start==end){
            return nums[start];
        }
        int[] dp=new int[nums.length];
        dp[start]=nums[start];
        dp[start+1]=Math.max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++){
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[end];
    }