动态规划编程题集合（leetcode)

亦凉 2023-09-25 19:02 10阅读 0赞

> 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。  
> 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。  
>   
> 输入：\[1,2,3,1\]  
> 输出：4  
> 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  
> 偷窃到的最高金额 = 1 + 3 = 4 。

dp\[i\]表示前 i 间房屋能偷窃到的最高总金额

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

> 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。  
> 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。  
> **输入：**nums = \[2,3,2\] **输出：**3 **解释：**你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。  
>

public int rob(int[] nums) {
            if(nums.length == 0) return 0;
            if(nums.length == 1) return nums[0];
            return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                    myRob(Arrays.copyOfRange(nums, 1, nums.length)));
        }
        private int myRob(int[] nums) {
              if(nums.length == 1) return nums[0];
            int[] dp=new int[nums.length];
            dp[0]=nums[0];
            dp[1]=Math.max(nums[0],nums[1]);
            for(int i=2;i<dp.length;i++){
                dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
            }
            return dp[nums.length-1];
        }

> 给你一个整数数组 prices ，其中 prices\[i\] 表示某支股票第 i 天的价格。  
> 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。  
> 返回 你能获得的 最大 利润 。  
>   
> 输入：prices = \[7,1,5,3,6,4\]  
> 输出：7  
> 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。  
> 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。  
> 总利润为 4 + 3 = 7 。  
>

采用官方说明

![11f8e1147d6917a49471cf143e953b18.png][]

本人这里写的代码和官方有点差别

dp\[i\]\[0\] 表示持有股的最大现金

dp\[i\]\[1\] 表示不持有股的最大现金

public int maxProfit(int[] prices) {
            int[][] dp=new int[prices.length][2];
            dp[0][0]=-prices[0];
            dp[0][1]=0;
            for(int i=1;i<prices.length;i++){
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
            }
            return dp[prices.length-1][1];
        }

贪心算法解决该题目

public int maxProfit(int[] prices) {
           int result=0;
           int min=prices[0];
           for(int i=1;i<prices.length;i++){
               if(prices[i]<min)
                   min=prices[i];
               else{
                   result+=prices[i]-min;
                   min=prices[i];
               }
           }
           return result;
        }

[11f8e1147d6917a49471cf143e953b18.png]: https://img-blog.csdnimg.cn/img_convert/11f8e1147d6917a49471cf143e953b18.png