五大常用算法--DP

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了五大常用算法--DP，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2300字，纯文字阅读大概需要4分钟。

内容图文

概念

【geekforgeeks】

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

动态规划是对于单纯的递归的一个主要优化方法。当我们看到递归解法对于同一个输入重复调用时，我们能通过动态规划方法重复优化。方法是简单存储子问题的结果，这样我们在后序用到它们的时候就不需要再重复计算了。这个简单的优化将时间复杂度从指数减少到了多项式。比如，如果我们写一下fibonacci数列的简单递归解法，我们得到了指数的时间复杂性，但是如果我们通过存储子问题进行优化，时间复杂性减少到了线性。

应用场景

通用解体思路

动态规划四要素：

1. 状态

2. 状态转移方程

3. 初始化

4. 结果

题目练习

Fibonacci数列 leetcode 509

最大连续子序列 leetcode 53

// 输入: [-2,1,-3,4,-1,2,1,-5,4],
// 输出: 6
// 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length, maxSum = nums[0];
    for(int i = 1; i < n; ++i) {
      if (nums[i - 1] > 0) nums[i] += nums[i - 1];
      maxSum = Math.max(nums[i], maxSum);
    }
    return maxSum;
  }
}

 

通配符匹配 leetcode 44

// 输入:
// s = "adceb"
// p = "*a*b"
// 输出: true
// 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        
        f[0][0] = true;
        for(int i = 1; i <= n; i++){
            f[0][i] = f[0][i - 1] && p.charAt(i - 1) == '*';
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    f[i][j] = f[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '*'){
                    f[i][j] = f[i][j - 1] || f[i - 1][j];
                }
            }
        }
        return f[m][n];
    }
}

参考资料

1. https://www.geeksforgeeks.org/dynamic-programming/

2. https://leetcode-cn.com/problems/wildcard-matching/solution/dong-tai-gui-hua-si-yao-su-by-a380922457-4/

3. https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode/

内容总结

以上是互联网集市为您收集整理的五大常用算法--DP全部内容，希望文章能够帮你解决五大常用算法--DP所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---