补充动态规划专题

dai · dai · commit e9cc28fe729f · 2021-03-31T17:15:53.000+08:00
diff --git a/28-算法面试专题-动态规划.md b/28-算法面试专题-动态规划.md
@@ -124,6 +124,129 @@ public class DPExampleUtil {
         // 最终返回dp表的0，bag位置，就是我们暴力递归的主函数调用
         return dp[0][bag];
     }
+
+
+    /**
+     * 2、最长递增子序列问题
+     * 问题描述：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
+     * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
+     * 
+     * 例如：nums = [10,9,2,5,3,7,101,18]， 返回结果是4。最长递增子序列是 [2,3,7,101]，因此长度为 4 。
+     **/
+    public int lengthOfLIS(int[] nums) {
+        if (nums.length == 0) {
+            return 0;
+        }
+        int[] dp = new int[nums.length];
+        dp[0] = 1;
+        // 全局最大
+        int max = 1;
+        for (int i = 1; i < nums.length; i++) {
+            // 默认每个元素的dp[i]都为1，表示自己形成的递增子序列
+            dp[i] = 1;
+
+
+            for (int j = 0; j < i; j++) {
+                // 如果在当前位置的前面，存在一个比自己小的元素，该元素的dp[j]加上当前元素形成的新的dp[j] + 1比dp[i]大。更新这个dp[i]。否则不更新
+                if (nums[i] > nums[j]) {
+                    dp[i] = Math.max(dp[i], dp[j] + 1);
+                }
+            }
+            // 最上层循环，每一轮检查是否需要更新全局max
+            max = Math.max(max, dp[i]);
+        }
+        return max;
+    }
+
+    /**
+     * 3、最大连续子数组的和（最大子序和）
+     *
+     * 问题描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
+     * 例如：nums = [-2,1,-3,4,-1,2,1,-5,4]，返回6。连续子数组 [4,-1,2,1] 的和最大，为 6 。
+     *
+     **/
+    public int maxSubArray(int[] nums) {
+        if(nums == null || nums.length == 0) {
+            return 0;
+        }
+
+        int N = nums.length;
+        // dp[i] 含义：子数组必须以i结尾的时候，所有可以得到的子数组中，最大累加和是多少？
+        int[] dp = new int[N];
+        dp[0] = nums[0];
+        // 记录全局最大的子数组的和
+        int max = dp[0];
+        for (int i = 1; i < N; i++) {
+            // 当前的值
+            int p1 = nums[i];
+            // 当前的值和上一个位置的最大和累加
+            int p2 = nums[i] + dp[i - 1];
+            // dp[i]等于，当前的值，和当前值与上一个位置最大和的累加，取大的
+            dp[i] = Math.max(p1, p2);
+            // 判断是否要更新全局最大值
+            max = Math.max(max, dp[i]);
+        }
+        // 返回全局最大值
+        return max;
+    }
+
+
+    /**
+     * 4、打家劫舍问题
+     * 
+     * 问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
+     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
+     *
+     * 示例输入：[1,2,3,1]， 输出4；偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
+     *
+     **/
+    public int rob(int[] nums) {
+
+        if(nums == null || nums.length == 0) {
+            return 0;
+        }
+        int[] dp = new int[nums.length];
+        
+        for(int i = 0; i < nums.length; i++) {
+            if(i == 0) {
+                dp[0] = nums[i];
+            }
+            if(i == 1) {
+                dp[1] = Math.max(dp[0], nums[i]);
+            }
+            if(i > 1) {
+                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
+            }
+        }
+        return dp[nums.length - 1];
+    }
+
+    /**
+     * 5、爬楼梯问题。
+     * 
+     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
+     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
+     *
+     **/
+    public int climbStairs(int n) {
+        if(n == 0) {
+            return 0;
+        }
+        if(n == 1) {
+            return 1;
+        }
+        if(n == 2) {
+            return 2;
+        }
+
+        int[] dp = new int[n + 1];
+        dp[1] = 1;
+        dp[2] = 2;
+        for(int i = 3; i <= n ; i++) {
+            dp[i] = dp[i-1] + dp[i-2];
+        }
+        return dp[n];
+    }
   
   
 }
