首页 › Java论坛 › hot100之动态规划下

仁者至上 發表於 2025-6-25 13:00:00

hot100之动态规划下

<h3 id="最长递增子序列300">最长递增子序列（300）</h3>
<pre><code class="language-java">class Solution {
    public int lengthOfLIS(int[] nums) {
      int res = 1;
      for(int num : nums){
            int idx = findLarge(nums, res, num);
            nums = num;
            if (idx == res) res++;   
      }
      
      return res;
    }

    private int findLarge(int[] nums, int rig, int target){
      int lef = -1;
      while (lef+1 &lt; rig){
            int mid = (lef + rig) / 2;
            if (nums &lt; target){
                lef = mid;
            }else rig = mid;
      }

      return rig;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>维护一个最小递增array（子序列）通过二分查找筛除坏值（比新插入值大）</p>
<p>利用二分查找优化查询</p>
<h3 id="乘积的最大子数组152">乘积的最大子数组（152）</h3>
<pre><code class="language-java">class Solution {
    public int maxProduct(int[] nums) {
      int n = nums.length;
      int[] postive_dp = new int ;
      int[] negative_dp = new int ;

      postive_dp = negative_dp = nums;
      for(int i = 1; i &lt; n; i++){
            postive_dp =max(postive_dp * nums, negative_dp * nums, nums);
            negative_dp = min(postive_dp * nums, negative_dp * nums, nums);
      }
      
      int res = Integer.MIN_VALUE;
      for (int postive_num : postive_dp){
            res = Math.max(res, postive_num);
      }
      return res;
    }

    private int max(int val1, int val2, int val3){
      val2 = Math.max(val2, val3);
      return Math.max(val1, val2);
    }

    private int min(int val1, int val2, int val3){
      val2 = Math.min(val2, val3);
      return Math.min(val1, val2);
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>因为num有&lt;正，负&gt;两种状态，即使前值算出来很小 但通过乘负数可以<em>将大局逆转吧</em></p>
<p>所以维护最大正数和最小负数两个dp，都是潜力</p>
<p>同样也可以优化内存， 因为只依赖前一个状态</p>
<h3 id="分割等和子集416">分割等和子集（416）</h3>
<pre><code class="language-java">class Solution {
    public boolean canPartition(int[] nums) {
      int sum = 0;
      for (int num: nums){
            sum += num;
      }
      if (sum % 2 != 0) return false;

      int target = sum / 2;
      boolean[] dp = new boolean;
      dp = true;
      for (int num : nums){
            for (int subSum = target; subSum &gt;= num; subSum--){
                dp |= dp;
                if (dp) return true;
            }
      }
      return false;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>背包问题</p>
<h3 id="最长有效括号32">最长有效括号(32)</h3>
<pre><code class="language-java">class Solution {
    public int longestValidParentheses(String s) {
      int n = s.length();
      Deque&lt;Integer&gt; stack = new ArrayDeque&lt;&gt;();
      stack.push(-1); // 避免第一个数值是左括号， 无值弹出
      int res = 0;

      for (int i = 0; i &lt; n; i++){
            if (s.charAt(i) == '('){
                stack.push(i);
            }else{
                stack.pop();
                if (stack.isEmpty()){
                  stack.push(i);
                }else{
                  res = Math.max(res, i - stack.peek());
                }
            }
      }

      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>没什么好想法，就用栈了</p>
<p>java 里栈的优化似乎不好，不如双端队列</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18947833

查看完整版本: hot100之动态规划下