当前位置: 首页 > news >正文

【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总

    《博主简介》

小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~
👍感谢小伙伴们点赞、关注!

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】,已更新31期,欢迎关注,持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

《------正文------》

这篇文章是博主在学习动态规划系列算法过程中精心总结的42页学习笔记,其中包含了动态规划的原理详解以及LeetCode中的动态规划题目汇总

免费分享给需要的下伙伴。原版文档获取方式见文末。

目录

介绍  

定义  

应用场景  

核心  

动态规划特点(三要素)  

通常的思考过程  

状态转移方程一般过程  

解题方法  

DP数组注意事项  

举例  

1.斐波拉契数列  

暴力递归:时间复杂度2^n指数级  

带备忘录的递归  

DP数组的迭代解法  

2.零钱兑换问题  

暴力解法  

带备忘录的递归  

DP数组迭代解法  

经典题目  

*最长回文子串  

*最长有效括号  

*不同的子序列  

*最长公共子序列  

*最长公共子串  

*最长上升子序列  

**编辑距离  

最长重复子数组  

完全平方数  

不同路径1  

不同路径2    

不同路径3(回溯)  

零钱兑换1  

零钱兑换2  

最大正方形    

最大矩形  

最大子序和  

三角形最小路径和  

乘积最大子数组  

打家劫舍  

最小路径和  

买卖股票问题  

买卖股票的最佳时机2    

使用最小花费爬楼梯  

解码方法  

赛车  

播放列表的数量  


介绍  

定义  

动态规划时一种运筹学方法,是在多轮决策过程中的最优方法。

应用场景  

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。

核心  

求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。

动态规划特点(三要素)  

1.最优子结构:原问题的最优解所包含的子问题的解也是最优的,通过子问题的最值得到原问题的最值。

2.存在重叠子问题:子问题间不独立(这是动态规划区别于分治的最大不同);如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算

3.无后效性:即后续的结果不会影响当前结果。

通常的思考过程  

动态规划没有标准的解题方法,但在宏观上有通用的方法论:

下面的 k 表示多轮决策的第 k 轮

1.分阶段,将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段,它们可以是不满足独立性的。    

2.找状态,选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变,更像是决策可能的结果。

3.做决策,确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作,例如 D2 的可能的决策动作是 D2 -> E2 和 D2 -> E3。

4.状态转移方程。这个步骤是动态规划最重要的核心,即 sk+1= uk(sk) 。

5.定目标。写出代表多轮决策目标的指标函数 Vk,n。

6.寻找终止条件。

状态转移方程一般过程  

状态转移方程:一般思考过程,明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。方程本质是数学的递推式

解题方法  

递归是一种自顶向下的求解方式,DP数组是一种自底向上的求解方式。

1.递归寻找暴力解:自顶向下求解;

2.通过备忘录memo优化递归过程,剔除重复计算,消除一下重叠子问题;

3.通过DP table 自底向上求解:主要是需要明确DP数组的含义定义,然后通过递推进行推导。

DP数组注意事项  

数组的遍历方向

# 正向遍历

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++)        

    for (int j = 0; j < n; j++)

        // 计算 dp[i][j]

# 反向遍历

for (int i = m - 1; i >= 0; i--)

    for (int j = n - 1; j >= 0; j--)

        // 计算 dp[i][j]

# 斜向遍历

for (int l = 2; l <= n; l++)

    for (int i = 0; i <= n - l; i++)

        int j = l + i - 1;

        // 计算 dp[i][j]

          

DP数组的递推计算过程需要注意两点:

1、遍历的过程中,所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置

主要就是看 base case 和最终结果的存储位置。

如:编辑距离问题:正向遍历    

回文子序列问题:从左至右斜着遍历,或从下向上从左到右遍历,都可以

    

举例  

1.斐波拉契数列  

暴力递归:时间复杂度2^n指数级  

def fib(n):

    if n <= 2:

        return 1

    return fib(n-1) + fib(n-2)

带备忘录的递归  

def fib(n):

    def helper(n):

        if n <= 2:

            return 1

        if n in memo:

            return memo[n]

        memo[n] = fib(n-1) + fib(n-2)

        return memo[n]

    memo = {} # 记录已经计算过的值,防止重复计算

    return helper(n)

DP数组的迭代解法  

上述递归过程是自顶向下求解的,dp数组则是自底向上求解的。

def fib(n):

    dp = [0 for _ in range(n+1)]        

    dp[1] = dp[2] = 1

    for i in range(3, n + 1):

        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

根据斐波那契数列的状态转移方程,当前状态只和之前的两个状态有关,其实并不需要那么长的一个 DP table 来存储所有的状态,只要想办法存储之前的两个状态就行了。所以,可以进一步优化,把空间复杂度降为 O(1):

def fib(n):

    if n <= 2:

        return 1

    prev = 1

    curr = 1

    for i in range(3,n+1):

        prev, curr = curr, prev + curr

    return curr

2.零钱兑换问题  

题目:给你 k 种面值的硬币,面值分别为 c1, c2 ... ck,每种硬币的数量无限,再给一个总金额 amount,问你最少需要几枚硬币凑出这个金额,如果不可能凑出,算法返回 -1 。

状态转移方程:

# 伪码框架

def coinChange(coins: List[int], amount: int):        

    # 定义:要凑出金额 n,至少要 dp(n) 个硬币

    def dp(n):

        # 做选择,选择需要硬币最少的那个结果

        for coin in coins:

            res = min(res, 1 + dp(n - coin))

        return res

    # 我们要求的问题是 dp(amount)

    return dp(amount)

实际代码:

暴力解法  

def coinChange(coins, amount):

    def dp(n):

        # 函数定义为目标金额为n时,所需的最少硬币数量

        # base case

        # 目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1

        if n == 0: return 0

        if n < 0: return -1

        # 求最小值,所以初始化结果为正无穷

        res = float('inf')

        for coin in coins:

            subpro = dp(n-coin)

            if subpro == -1:

                # 子问题无解,跳过

                continue

            res = min(res, 1 + subpro)

        return res if res != float('inf') else -1

    return dp(amount)

带备忘录的递归  

def coinChange(coins, amount):        

    def dp(n):

        # 函数定义为目标金额为n时,所需的最少硬币数量

        # base case

        # 目标金额为 0 时,所需硬币数量为 0;当目标金额小于 0 时,无解,返回 -1

        if n == 0: return 0

        if n < 0: return -1

        if n in memo:

            return memo[n]

        # 求最小值,所以初始化结果为正无穷

        res = float('inf')

        for coin in coins:

            subpro = dp(n-coin)

            if subpro == -1:

                # 子问题无解,跳过

                continue

            res = min(res, 1 + subpro)

        memo[n] = res if res != float('inf') else -1

        return memo[n]

    memo = {}

    return dp(amount)

DP数组迭代解法  

dp[i] = x 表示,当目标金额为 i 时,至少需要 x 枚硬币。

def coinChange(coins, amount):

# 数组大小为 amount + 1,初始值也为 amount + 1

# 因为总的零钱个数不会超过amount,所以初始化amount + 1即可

    dp = [amount + 1 for _ in (amount + 1)]

    dp[0] = 0

    for i in range(len(dp)):

        #  内层 for循环,求解的是所有子问题 + 1 的最小值

        for coin in coins:

            # 子问题无解,跳过

            if i - coin < 0:

                continue

            dp[i] = min(dp[i],1+dp[i-coin])        

    if dp[amount] == amount + 1:

        return  -1

    else:

        return dp[amount]

注:dp 数组初始化为 amount + 1 呢,因为凑成 amount 金额的硬币数最多只可能等于 amount(全用 1 元面值的硬币),所以初始化为 amount + 1 就相当于初始化为正无穷,便于后续取最小值。

这个题目相当于是组合问题,每个硬币可以用多次,一共有多少种组合。

说明:前k个硬币凑齐金额i的组合数等于前k-1个硬币凑齐金额i的组合数加上在原来i-k的基础上使用硬币的组合数。说的更加直白一点,那就是用前k的硬币凑齐金额i,要分为两种情况开率,一种是没有用前k-1个硬币就凑齐了,一种是前面已经凑到了i-k,现在就差第k个硬币了。

DP[i] = DP[i] + DP[i-k]:

式子右边的DP[i]表示不使用第K个金币的和为i的组合, DP[i-k]表示使用金币k的和为i的组合数。

          

第 39 题问的是所有的组合列表,需要知道每一个组合是什么?,应该使用 回溯算法 求解,并且存储每一个组合;

第 518 题问的是组合有多少种,而不是问具体的解。应该使用 动态规划 求解

class Solution:

    def change(self, amount: int, coins: List[int]) -> int:        

        # 子问题:对于硬币从0到k,我们必须使用第k个硬币的时候,当前金额的组合数

        # 状态数组DP[i]表示对于第k个硬币能凑的组合数

        # 转移方程DP[i] = DP[i] + DP[i-k]

        dp = [0] * (amount + 1)

        dp[0] = 1

        for coin in coins:

            for x in range(1, amount + 1):

                 if x < coin: continue   # coin不能大于amount

                dp[x] += dp[x - coin]

        return dp[amount]

这个题实际上是排列问题,因为顺序不同的话视为不同的组合。

class Solution:

    def combinationSum4(self, nums: List[int], target: int) -> int:

        dp = [0] * (target + 1)        

        dp[0] = 1

        for x in range(1, target + 1):

            for num in nums:

                if x < num:continue

                dp[x] += dp[x - num]

        return dp[target]

          

参考:

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-iihe-pa-lou-ti-wen-ti-dao-di-yo/

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/

总结:

518零钱兑换2是一个组合问题,DP先遍历零钱列表,再遍历amount金额数;

def change(coins,amount):

    # 求的是组合数

    dp = [0 for _ in range(amount+1)]

    dp[0] = 1

    for coin in coins:  # 枚举硬币

        for i in range(amount + 1):  # 枚举金额

            if i < coin: continue #coin不能大于amount

            dp[i] = dp[i] + dp[i - coin]

    return dp[amount]

          

377组合个数是一个排列问题, DP先遍历amount金额数,再遍历零钱列表。

def change(coins,amount):

    # 求的是排列数

    dp = [0 for _ in range(amount+1)]

    dp[0] = 1        

    for i in range(amount + 1):  # 枚举金额

        for coin in coins:  #枚举硬币

            if i < coin: continue #coin不能大于amount

            dp[i] = dp[i] + dp[i - coin]

    return dp[amount]

举例:

在LeetCode上有两道题目非常类似,分别是

70.爬楼梯  --排列问题

518. 零钱兑换 II  -- 组合问题

如果我们把每次可走步数/零钱面额限制为[1,2], 把楼梯高度/总金额限制为3. 那么这两道题目就可以抽象成"给定[1,2], 求组合成3的组合数和排列数"。

爬台阶问题通用模板

def climbStairs(n):

    # 爬台阶问题通用模板

    dp = [0 for _ in range(n + 1)]

    dp[0] = 1

    steps = [1,2,4,5]

    for i in range(n+1):

        for j in range(len(steps)):

            if i < steps[j]: continue # 台阶少于跨越的步数

            dp[i] = dp[i] + dp[i-steps[j]]

    return dp[n]

              

经典题目  

*最长回文子串  

          

# 动态规划

# 用 P(i,j)P(i,j) 表示字符串 s的第 i 到 j 个字母组成的串(下文表示成 s[i:j])是否为回文串

class Solution:

    def longestPalindrome(self, s: str) -> str:

        n = len(s)

        dp = [[False] * n for _ in range(n)]

        ans = ""

        # 枚举子串的长度 l+1

        for l in range(n):

            # 枚举子串的起始位置 i,这样可以通过 j=i+l 得到子串的结束位置

            for i in range(n-l):

                j = i + l

                if l == 0:

                    dp[i][j] = True        

                elif l == 1:

                    dp[i][j] = (s[i] == s[j])

                else:

                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])

                if dp[i][j] and l + 1 > len(ans):

                    ans = s[i:j+1]

        return ans

                  

                  

# 中心扩展法

class Solution:

    def expandAroundCenter(self, s, left, right):

        while left >= 0 and right < len(s) and s[left] == s[right]:

            left -= 1

            right += 1

        return left + 1, right - 1

                  

    def longestPalindrome(self, s: str) -> str:

        # 中心扩展法,每个字符从中心往两边扩展,分奇偶

        start, end = 0, 0

        for i in range(len(s)):

            left1, right1 = self.expandAroundCenter(s, i, i) # 以当前字符为中心

            left2, right2 = self.expandAroundCenter(s, i, i + 1) # 以当前字符与后面一个字符为中心

            if right1 - left1 > end - start:

                start, end = left1, right1

            if right2 - left2 > end - start:

                start, end = left2, right2

        return s[start: end + 1]

              

*最长有效括号  

法一:动态规划

class Solution:

    def longestValidParentheses(self, s: str) -> int:

        # 动态规划

        # dp[i] 表示以i结尾的最长有效括号长度,‘(’对应的一定是0

        n = len(s)

        if n == 0:

            return 0

        dp = [0] * n

        for i in range(1,n):

            # i- dp[i-1] -1是与当前')'对称的位置

            # dp[i-dp[i-1]-2] 表示与当前')'对称的位置前面的有效括号长度,需加上

            if s[i]==')' and i - dp[i-1] - 1>=0 and s[i - dp[i-1] - 1] == '(':

                dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2

        return max(dp)

          

法二:栈

class Solution:

    def longestValidParentheses(self, s: str) -> int:

        # 栈来实现

        stack = [-1]

        length = 0

        max_length = 0        

        for i in range(len(s)):

            if s[i] == '(':

                stack.append(i)

            else:

                stack.pop()

                if not stack:

                # 栈为空,则添加当前右括号的索引入栈,为分割标识

                    stack.append(i)

                else:

                    length = i - stack[-1]

                    max_length = max(max_length, length)

        return max_length

          

*不同的子序列  

              

class Solution:

    def numDistinct(self, s: str, t: str) -> int:

        # S中T出现的个数

        # dp[i][j]表示t的前i个字符串可以由s的前j个字符串组成多少个

        n = len(s) # 列

        m = len(t) # 行

        dp = [[0] * (n+1) for _ in range(m+1)]

        for j in range(n+1):

            dp[0][j] = 1

        for i in range(1,m + 1):

            for j in range(1, n + 1):

                if t[i-1] == s[j-1]:

# 对应于两种情况,s选择当前字母和不选择当前字母

# s选择当前字母dp[i-1][j-1]

# s不选择当前字母 dp[i][j-1]

                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

                else:

                    dp[i][j] = dp[i][j-1]

        return dp[-1][-1]

              

          

*最长公共子序列  

参考:https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/    

# 动态规划

class Solution:

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        m = len(text1)

        n = len(text2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m+1):

            for j in range(1, n+1):

                if text1[i-1] == text2[j-1]:

                    dp[i][j] = dp[i-1][j-1] + 1

                else:

                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])

        return dp[-1][-1]

                  

# 递归

class Solution:

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        # 递归

        memo = {} #备忘录

        def dp(i, j):

            if i == -1 or j == -1:

                return 0

            if (i,j) in memo:

                return memo[(i,j)]

            if text1[i] == text2[j]:

                memo[(i,j)] = dp(i-1, j-1) + 1

            else:

                memo[(i,j)] = max(dp(i-1, j), dp(i,j-1))

            return memo[(i,j)]

        return dp(len(text1)-1,len(text2)-1)

          

*最长公共子串  

注意:与子序列不相同的是子串是连续的,子序列可以是不连续的。    

def LCS(s1,s2):

    #dp[i][j]表示以s1的i及s2的j结尾的最长公共子串长度

    #如果s1[i-1] != s2[j-1] 则,dp[i][j] = 0

    m = len(s1)

    n = len(s2)

    dp = [[0] *(n+1) for _ in range(m + 1)]

    maxLen = 0

    end = 0

    for i in range(1,m+1):

        for j in range(1,n+1):

            if s1[i-1] == s2[j-1]:

                dp[i][j] = dp[i-1][j-1] + 1

            else:

                dp[i][j] = 0

            if dp[i][j] > maxLen:

                maxLen = dp[i][j]

                end = j-1

    if maxLen == 0:

        return ''

    else:

        return s2[end - maxLen + 1:end + 1]

              

          

*最长上升子序列  

class Solution:

    def lengthOfLIS(self, nums: List[int]) -> int:

        if not nums:

            return 0

        # dp[i]表示以第i个元素结尾的最长递增子序列长度

        n = len(nums)

        dp = [1 for _ in range(n)]

        for i in range(n):

            for j in range(i):

                if nums[i] > nums[j]:

                    dp[i] = max(dp[i],dp[j] + 1)

        return max(dp)

              

**编辑距离  

class Solution:

    def minDistance(self, word1: str, word2: str) -> int:

        # DP递推方程        

        # 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离

        m = len(word1)

        n = len(word2)

        dp = [[0]*(n+1) for i in range(m+1)]

        for i in range(m+1):

            dp[i][0] = i

        for j in range(n+1):

            dp[0][j] = j

        for i in range(1, m+1):

            for j in range(1,n+1):

                if word1[i-1] == word2[j-1]:

                    dp[i][j] = dp[i-1][j-1]

                else:

                    dp[i][j] = min(dp[i-1][j]+1,

                    dp[i][j-1]+1,

                    dp[i-1][j-1]+1)

        return dp[m][n]

# 递归写法

class Solution:

    def minDistance(self, word1: str, word2: str) -> int:

                  

        def dp(i,j):

            if i == -1:

                return j + 1

            if j == -1:

                return i + 1

            if (i,j) in memo:

                return memo[(i,j)]

            if word1[i] == word2[j]:

                memo[(i,j)] = dp(i-1,j-1)

            else:

                memo[(i,j)] = min(dp(i-1,j)+ 1,

                dp(i,j-1) + 1,

                dp(i-1,j-1) + 1)

            return memo[(i,j)]

        memo = {}

        res = dp(len(word1)-1,len(word2)-1)

        return res

              

最长重复子数组  

class Solution:

    def findLength(self, A: List[int], B: List[int]) -> int:

        # p[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀,那么答案即为所有 dp[i][j] 中的最大值。

        # 如果 A[i] == B[j],那么 dp[i][j] = dp[i + 1][j + 1] + 1,否则 dp[i][j] = 0。

        # 考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到,所以我们需要倒过来,首先计算 dp[len(A) - 1][len(B) - 1],最后计算 dp[0][0]

        n, m = len(A), len(B)

        dp = [[0] * (m + 1) for _ in range(n + 1)]

        ans = 0

        for i in range(n - 1, -1, -1):

            for j in range(m - 1, -1, -1):        

                dp[i][j] = dp[i + 1][j + 1] + 1 if A[i] == B[j] else 0

                ans = max(ans, dp[i][j])

        return ans

          

完全平方数  

class Solution:

    def numSquares(self, n: int) -> int:

        dp = [0] * (n + 1)

        for i in range(1, n + 1):

            dp[i] = i  #最坏的情况就是全是1

            j = 1

            while i - j*j >= 0:

                dp[i] = min(dp[i], dp[i - j * j] + 1)

                j += 1

        return dp[n]

              

不同路径1  

class Solution:

    def uniquePaths(self, m: int, n: int) -> int:

        dp = [[0 for i in range(n)] for _ in range(m)]

        for i in range(m):

            dp[i][0] = 1

        for j in range(n):

            dp[0][j] = 1

        for i in range(1,m):

            for j in range(1,n):

                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[-1][-1]

不同路径2    

class Solution:

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m = len(obstacleGrid)

        n = len(obstacleGrid[0])

        zero_loc = {(i,j) for i in range(m) for j in range(n) if obstacleGrid[i][j] == 1}

        dp = [[0] * n for i in range(m)]

        for i in range(m):

            # 初始化第一列,只要碰到一个1,那么后边都无法走到

            if obstacleGrid[i][0] == 1:

                break

            dp[i][0] = 1

        for j in range(n):

            #初始化第一行,只要碰到一个1,那么后边都无法走到

            if obstacleGrid[0][j] == 1:

                break

            dp[0][j] = 1

        for i in range(1,m):

            for j in range(1,n):

                if (i,j) in zero_loc:        

                    dp[i][j] = 0

                else:

                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[-1][-1]

                  

class Solution:

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:

        m = len(obstacleGrid)

        n =len(obstacleGrid[0])

        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:

            return 0

        dp = [[0] * n for _ in range(m)]

        for i in range(m):

            if obstacleGrid[i][0] == 0:

                dp[i][0] = 1

            else:

                break

        for j in range(n):

            if obstacleGrid[0][j] == 0:

                dp[0][j] = 1

            else:

                break

        for i in range(1,m):

            for j in range(1,n):        

                if obstacleGrid[i][j] == 1:

                    dp[i][j] = 0

                    continue

                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[-1][-1]

          

不同路径3(回溯)  

class Solution:

    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        # 注意每一个无障碍的格子都需要通过一次

        start_x = 0        

        start_y = 0

        steps = 1

        m = len(grid)

        n = len(grid[0])

        # 遍历获取起始位置和统计总步数

        for i in range(m):

            for j in range(n):

                if grid[i][j] == 1:

                    start_x = i

                    start_y = j

                    continue

                if grid[i][j] == 0:

                    steps += 1

        def DFS(x,y,cur_step, grid):

            # 排除越界的情况和遇到障碍的情况

            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == -1:

                return 0

            if grid[x][y] == 2:

                # 走到2的位置,且步数为0,表示经过了所有的无障碍格子,是一种方案

                return 1 if cur_step == 0 else 0

            grid[x][y] = -1 # 将已经走过的标记为障碍

            res = DFS(x - 1, y, cur_step - 1, grid) + DFS(x + 1, y, cur_step - 1, grid) \

                   + DFS(x, y - 1, cur_step - 1, grid) \

                   + DFS(x, y + 1, cur_step - 1, grid)

            # 回溯

            grid[x][y] = 0

            return res

        return DFS(start_x,start_y,steps,grid)

              

零钱兑换1  

class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:

        #dp[i] = x 表示金额i最少需要x个金币

        dp = [amount + 1 for i in range(amount + 1)]

        dp[0] = 0

        for i in range(amount+1):

            for coin in coins:

                if i - coin < 0:

                    continue

                dp[i] = min(dp[i],dp[i-coin] + 1)

        if dp[amount] == amount + 1:

            return -1

        else:

            return dp[amount]

              

零钱兑换2  

class Solution:

    def change(self, amount: int, coins: List[int]) -> int:

        # 子问题:对于硬币从0到k,我们必须使用第k个硬币的时候,当前金额的组合数

        # 状态数组DP[i]表示对于第k个硬币能凑的组合数

        # 转移方程DP[i] = DP[i] + DP[i-k]

        dp = [0] * (amount + 1)

        dp[0] = 1

        for coin in coins:

            for x in range(coin, amount + 1):

                dp[x] += dp[x - coin]

        return dp[amount]

最大正方形    

class Solution:

    def maximalSquare(self, matrix: List[List[str]]) -> int:

        # 用 dp(i, j) 表示以 (i, j)为右下角,且只包含 1的正方形的边长最大值

        if len(matrix) == 0 or len(matrix[0]) == 0:

            return 0

        maxSide = 0

        rows, columns = len(matrix), len(matrix[0])

        dp = [[0] * columns for _ in range(rows)]

        for i in range(rows):

            for j in range(columns):

                if matrix[i][j] == '1':

                    if i == 0 or j == 0:

                        dp[i][j] = 1

                    else:

                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

                    maxSide = max(maxSide, dp[i][j])

        maxSquare = maxSide * maxSide

        return maxSquare

              

最大矩形  

class Solution:

    def maximalRectangle(self, matrix: List[List[str]]) -> int:

        #时间复杂度 : O(NM)。每次对于N的迭代我们会对M迭代常数次

        if not matrix: return 0

        m = len(matrix)

        n = len(matrix[0])

                  

        left = [0] * n # initialize left as the leftmost boundary possible

        right = [n] * n # initialize right as the rightmost boundary possible

        height = [0] * n

        maxarea = 0

        for i in range(m):

            cur_left, cur_right = 0, n

            # update height

            for j in range(n):

                if matrix[i][j] == '1': height[j] += 1

                else: height[j] = 0

            # update left        

            for j in range(n):

                if matrix[i][j] == '1': left[j] = max(left[j], cur_left)

                else:

                    left[j] = 0

                    cur_left = j + 1

            # update right

            for j in range(n-1, -1, -1):

                if matrix[i][j] == '1': right[j] = min(right[j], cur_right)

                else:

                    right[j] = n

                    cur_right = j

            # update the area

            for j in range(n):

                maxarea = max(maxarea, height[j] * (right[j] - left[j]))

                  

        return maxarea

          

          

最大子序和  

class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

        # dp[i] 表示以小标i为结尾的最大连续子序列的和dp[j] = max(nums[j],dp[j-1] + nums[j])

        if len(nums) == 0:

            return 0

        if len(nums) == 1:

            return nums[0]

        n = len(nums)        

        dp = [float('-inf')] * n

        dp[0] = nums[0]

        for j in range(1,n):

            dp[j] = max(nums[j],dp[j-1] + nums[j])

        return max(dp)

三角形最小路径和  

#法一

class Solution:

    def minimumTotal(self, triangle: List[List[int]]) -> int:

        n = len(triangle)

        f = [[0] * n for _ in range(n)]

        f[0][0] = triangle[0][0]

                  

        for i in range(1, n):        

            f[i][0] = f[i - 1][0] + triangle[i][0]

            for j in range(1, i):

                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]

            f[i][i] = f[i - 1][i - 1] + triangle[i][i]     

        return min(f[n - 1])

                  

#法二

class Solution:

    def minimumTotal(self, triangle: List[List[int]]) -> int:

        n = len(triangle)

        f = [0] * n

        f[0] = triangle[0][0]

                  

        for i in range(1, n):

            f[i] = f[i - 1] + triangle[i][i]

            for j in range(i - 1, 0, -1):

                f[j] = min(f[j - 1], f[j]) + triangle[i][j]

            f[0] += triangle[i][0]

        return min(f)

          

              

乘积最大子数组  

class Solution:

    def maxProduct(self, nums: List[int]) -> int:

        n = len(nums)

        if n == 0:

            return 0

        dpMax = [float('-inf')] * n  # 存储以i结尾的最大连续子数组乘积

        dpMax[0] = nums[0]

        dpMin = [float('inf')] * n # 存储以i结尾的最小连续子数组乘积,存在负负得正的情况

        dpMin[0] = nums[0]

        for i in range(1,n):

            dpMax[i] = max(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i])

            dpMin[i] = min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i], nums[i])

        return max(dpMax)

              

打家劫舍  

class Solution:

    def rob(self, nums: List[int]) -> int:

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

        #dp[i] = max(dp[i-1],dp[i-2]+nums[i]) 

        n = len(nums)

        if n==0:

            return 0

        if n==1:

            return nums[0]

        dp = [0]* n

        dp[0] = nums[0]

        dp[1] = max(nums[0],nums[1])

        for i in range(2,n):

            dp[i] = max(dp[i-1],dp[i-2]+nums[i])

        return dp[n-1]

              

最小路径和  

class Solution:

def minPathSum(self, grid: List[List[int]]) -> int:

    # dp[i][j]表示达到i,j点的最小路径和

        m = len(grid)

        n = len(grid[0])

        dp = [[0]*n for _ in range(m)]

        dp[0][0] = grid[0][0]

        for i in range(1, m):

            dp[i][0] = dp[i-1][0] + grid[i][0]

        for i in range(1, n):

            dp[0][i] = dp[0][i-1] + grid[0][i]

        for i in range(1, m):

            for j in range(1, n):

                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]

        return dp[-1][-1]

              

买卖股票问题  

# 动态规划

 class Solution:

    def maxProfit(self, prices: List[int]) -> int:

        # 动态规划dp[i] 表示前 i 天的最大利润

        n = len(prices)

        if n == 0: return 0 # 边界条件

        dp = [0] * n

        minprice = prices[0]

        for i in range(1, n):

            minprice = min(minprice, prices[i])

            dp[i] = max(dp[i - 1], prices[i] - minprice)

        return dp[-1]

                  

# 方法二

def maxProfit(self, prices: List[int]) -> int:

    minprice = float('inf') # 正无穷  负无穷 float("-inf")

    maxprofit = 0

    for p in prices:

        minprice = min(minprice, p)

        maxprofit = max(maxprofit, p-minprice)

    return maxprofit

买卖股票的最佳时机2    

          

def maxProfit(self, prices: List[int]) -> int:

    #在第二次买的时候,价格其实是考虑用了第一次赚的钱去补贴一部分的

    buy_1 = buy_2 = float('inf') # 第一二次买之前的最低价

    pro_1 = pro_2 = 0

   

    for p in prices:

        buy_1 = min(buy_1, p)

        pro_1 = max(pro_1, p - buy_1)

        buy_2 = min(buy_2, p - pro_1) # p - pro_1 是用第一次的钱抵消了一部分第二次买的钱

        pro_2 = max(pro_2, p - buy_2)

    return pro_2

                  

              

使用最小花费爬楼梯  

class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        # 踏上第i级台阶的最小花费,用dp[i]表示

        # 初始条件:

        # 最后一步踏上第0级台阶,最小花费dp[0] = cost[0]。

        # 最后一步踏上第1级台阶有两个选择:

        # 可以分别踏上第0级与第1级台阶,花费cost[0] + cost[1];

        # 也可以从地面开始迈两步直接踏上第1级台阶,花费cost[1]。

        n = len(cost)

        dp = [0] * n

        dp[0], dp[1] = cost[0], cost[1]

        for i in range(2, n):

            dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i]

        return min(dp[-2], dp[-1])

              

解码方法  

class Solution:

    def numDecodings(self, s: str) -> int:

        if s[0] == '0':

            return 0

        n = len(s)

        dp = [0] * (n + 1)

        dp[0] = 1

        dp[-1] = 1

        for i in range(1,n):

            # '0'只有10和20才有对应字母,不然 返回 0        

            if s[i] == '0':

                if s[i-1]=='1' or s[i-1]=='2':

                    dp[i] = dp[i-2]

                else:

                    return 0

            else:

                if s[i-1] == '1' or (s[i-1] =='2' and s[i] < '7'):

                    # i-1与i 可以结合或者分开

                    dp[i] = dp[i-1] + dp[i-2]

                else:

                    # i-1与i 必须分开

                    dp[i] = dp[i-1]

        return dp[-2]

              

赛车  

    

    

# 动态规划 DP

class Solution(object):

    def racecar(self, target):

        # dp[x] 表示到达位置 x 的最短指令长度

        dp = [0, 1] + [float('inf')] * target

        for t in range(2, target + 1):

            k = t.bit_length()

            if t == 2**k - 1:

                dp[t] = k

                continue

            for j in range(k - 1):

                # t - (2**(k-1)-2**j) 为剩余距离,dp[t - 2**(k - 1) + 2**j]表示这个剩余距离需要使用的最少命令数,加上已经使用的 k - 1 + j + 2

                # 由于返回使用的j不确定,因此需要通过遍历【0,k-2】确定dp[t]的最小值        

                dp[t] = min(dp[t], dp[t - 2**(k - 1) + 2**j] + k - 1 + j + 2)

            # 2**k - 1 - t 表示剩余需要按返回的距离,dp[2**k - 1 - t]表示走剩余距离需要要使用的最少命令数,加上已经使用的k+1

            dp[t] = min(dp[t], dp[2**k - 1 - t] + k + 1)

        return dp[target]

                  

# 递归写法

class Solution:

    dp = {0: 0}

    def racecar(self, target: int) -> int:

        t = target

        if t in self.dp:

            return self.dp[t]

        n = t.bit_length()

        if 2**n - 1 == t:

            self.dp[t] = n

        else:

            self.dp[t] = self.racecar(2**n - 1 - t) + n + 1

            for m in range(n - 1):

                self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)

        return self.dp[t]

          

              

播放列表的数量  

class Solution:

    def numMusicPlaylists(self, N: int, L: int, K: int) -> int:

        mod = 10 ** 9 + 7

        # dp[i][j] 表示用j首不同的歌填充长度为i的歌单数目

        dp = [[0] * (N + 1) for _ in range(L + 1)]

        dp[0][0] = 1

        for i in range(1, L + 1):

            for j in range(1, N + 1):

                # 分成两种情况,我们可以播放没有播放过的歌也可以是播放过的

                # 如果当前的歌和前面的都不一样,歌单前i-1首歌只包括了j-1首不同的歌曲,

                # 那么当前的选择有dp[i-1][j-1] * (N-j+1)

                # 如果不是,那么就是选择之前的一首歌,之前最近的K首是不能选的,只能选择j-K前面的歌曲,(j 首歌,最近的 K 首不可以播放)

                # 所以选择就是dp[i-1][j] * max(0, j-K)        

                dp[i][j] = (dp[i-1][j-1] * (N - j + 1) + dp[i-1][j] * max(0, j - K)) % mod

        return dp[-1][-1]

   

关于本篇文章大家有任何建议或意见,欢迎在评论区留言交流!

觉得不错的小伙伴,感谢点赞、关注加收藏哦!

欢迎关注下方GZH:阿旭算法与机器学习,发送:【动态规划】,即可获取原版文档。欢迎小伙伴共同学习交流~

          

相关文章:

【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推荐--…...

Python正则的匹配与替换

import re 查找时的注意事项&#xff0c;要查找的内容左右两边打出来&#xff0c;用真正的字符&#xff0c;不要用.*?&#xff0c;离查找内容远一点&#xff0c;再用.*? a /aksj<a>哈哈哈<a><p>拉阿鲁<p>\.askjp b re.findall(<a>(.*?)<…...

解决ELement-UI懒加载三级联动数据不回显(天坑)

最老是遇到这类问题头有点大,最后也是解决了,为铁铁们总结了一下几点 一.查看数据类型是否一致 未选择下 选择下 二.处理数据时使用this.$set方法来动态地设置实例中的属性&#xff0c;以确保其响应式 三.绑定v-if 确保每次重新加载 四.绑定key 五.完整代码...

【数据结构和算法】找出两数组的不同

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 哈希类算法题注意事项 2.2 方法一&#xff1a;哈希法 三、代码 3.1 方法一&#xff1a;哈希法 四…...

基于Python的B站排行榜大数据分析与可视化系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 本文介绍了一项基于Python的B站排行榜大数据分析与可视化系统的研究。通过网络爬虫技术&#xff0c;系统能够自动分析B站网址&#xff0c;提取大量相关文本信息并存储在系统中。通过对这些信息进行…...

MySQL一些常用命令

1、登录本地MySQL #一种是 mysql -u root -p; #(输入密码后回车)#另一种是 mysql -uroot -p123456; #(在-p后面直接带上密码)2、启动MySQL服务 net start mysql; 3、关闭MySQL服务&#xff1a; net stop mysql; 4、创建数据库 create database 数据库名; 5、创建数据…...

WPF 新手指引弹窗

新手指引弹窗介绍 我们在第一次使用某个软件时&#xff0c;通常会有一个“新手指引”教学引导。WPF实现“新手指引”非常方便&#xff0c;且非常有趣。接下来我们就开始制作一个简单的”新手指引”(代码简单易懂&#xff0c;便于移植)&#xff0c;引用到我们的项目中又可添加一…...

py注册登录界面

代码分析 引入tkinter库&#xff0c;并从中导入messagebox模块。 read_users()函数用于读取存储用户信息的文本文件"users.txt"。它打开文件并逐行读取&#xff0c;将每行的用户名和密码以空格分隔后存储在一个列表中&#xff0c;最后返回该列表。 login(username,…...

基于电商场景的高并发RocketMQ实战-Consumer端队列负载均衡分配机制、并发消费以及消费进度提交

&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308; 【11来了】文章导读地址&#xff1a;点击查看文章导读&#xff01; &#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f341;&#x1f3…...

【Java开发岗面试】八股文—数据库MySQLRedis

声明&#xff1a; 背景&#xff1a;本人为24届双非硕校招生&#xff0c;已经完整经历了一次秋招&#xff0c;拿到了三个offer。本专题旨在分享自己的一些Java开发岗面试经验&#xff08;主要是校招&#xff09;&#xff0c;包括我自己总结的八股文、算法、项目介绍、HR面和面试…...

IntelliJ IDEA [设置] 隐藏 .idea 等 .XXX 文件夹

文章目录 1. 问题描述2. 解决办法3. 最后效果4. 特殊处理&#xff08;正常不需要此步骤&#xff09;总结 我们使用 IntelliJ IDEA 导入项目的时候&#xff0c;经常会看到一些 .XXX 的文件夹&#xff08;例如&#xff1a;.idea&#xff0c;.mvn&#xff0c;.gradle 等&#xff0…...

每日一题——LeetCode961

方法一 排序法&#xff1a; 2*n长度的数组里面有一个元素重复了n次&#xff0c;那么将数组排序&#xff0c;求出排序后数组的中间值&#xff08;因为长度是偶数&#xff0c;没有刚好的中间值&#xff0c;默认求的中间值是偏左边的那个&#xff09;那么共有三种情况&#xff1a;…...

基于Unity Editor开发一个技能编辑器可能涉及到的内容

基于Unity Editor开发一个技能编辑器&#xff0c;涉及到的方面较多&#xff0c;涵盖了Unity自身的GUI框架、序列化系统、自定义编辑器、脚本调用与数据存储等。下面是几个关键点和你可能会用到的类以及API&#xff1a; 自定义Inspector&#xff1a; 使用Editor类来重写组件的I…...

Ubuntu 22.04 安装ftp实现与windows文件互传

Ubuntu 22.04 安装ftp实现与windows文件互传 1、配置安装 安装&#xff1a; sudo apt install vsftpd -y使能开机自启&#xff1a; sudo systemctl enable vsftpd 启动&#xff1a; sudo systemctl start vsftpd创建ftp工作目录&#xff1a; sudo mkdir -p /home/ftp/uftp…...

EasyPoi使用案例

EasyPoi使用案例 easypoi旨在简化Excel和Word的操作。基于注解的导入导出&#xff0c;修改注解就可以修改Excel&#xff1b;支持常用的样式自定义&#xff1b;基于map可以灵活定义表头字段&#xff1b;支持一对多的导入导出&#xff1b;支持模板的导出&#xff1b;支持HTML/Exc…...

分布式系统架构设计之分布式数据存储的分类和组合策略

在现下科技发展迅猛的背景下&#xff0c;分布式系统已经成为许多大规模应用和服务的基础架构。分布式架构的设计不仅仅是一项技术挑战&#xff0c;更是对数据存储、管理和处理能力的严峻考验。随着云原生、大数据、人工智能等技术的崛起&#xff0c;分布式系统对于数据的高效存…...

javaEE -18(11000字 JavaScript入门 - 3)

一&#xff1a;事件 &#xff08;高级&#xff09; 1.1 注册事件&#xff08;绑定事件&#xff09; 给元素添加事件&#xff0c;称为注册事件或者绑定事件&#xff0c;注册事件有两种方式&#xff1a;传统方式和方法监听注册方式 传统注册方式 &#xff1a; 利用 on 开头的…...

LangChain.js 实战系列:入门介绍

&#x1f4dd; LangChain.js 是一个快速开发大模型应用的框架&#xff0c;它提供了一系列强大的功能和工具&#xff0c;使得开发者能够更加高效地构建复杂的应用程序。LangChain.js 实战系列文章将介绍在实际项目中使用 LangChain.js 时的一些方法和技巧。 LangChain.js 是一个…...

pyCharm 打印控制台中文乱码解决办法

解决方法 在 "File" -> "Settings" 中的控制台设置&#xff1a; 在 "File" -> "Settings" 中&#xff0c;你可以找到 "Editor" -> "General" -> "Console"。在这里&#xff0c;你可能会找到…...

计算机基础--Linux详解

一概述 Linux是一种自由和开放源码的类UNIX操作系统。它是由林纳斯托瓦兹于1991年首次发布的&#xff0c;并从那时起在全球范围内得到了广泛的应用和开发。Linux具有强大的可定制性&#xff0c;可以运行在各种硬件平台上&#xff0c;包括x86、ARM、MIPS等。它不仅广泛应用于服…...

基于OpenAI的Whisper构建的高效语音识别模型:faster-whisper

1 faster-whisper介绍 faster-whisper是基于OpenAI的Whisper模型的高效实现&#xff0c;它利用CTranslate2&#xff0c;一个专为Transformer模型设计的快速推理引擎。这种实现不仅提高了语音识别的速度&#xff0c;还优化了内存使用效率。faster-whisper的核心优势在于其能够在…...

cfa一级考生复习经验分享系列(十六)

写在前面&#xff1a;并不鼓励大家在考前一个月才开始复习&#xff0c;不过&#xff0c;既然已经逼到了绝境&#xff0c;灰心丧气也没有用&#xff0c;不如放手一搏&#xff01; 首先说一下我的背景&#xff0c;工作金融机构的it&#xff0c;和cfa基本没关系&#xff0c;本硕计…...

数模学习day05-插值算法

插值算法有什么作用呢&#xff1f; 答&#xff1a;数模比赛中&#xff0c;常常需要根据已知的函数点进行数据、模型的处理和分析&#xff0c;而有时候现有的数据是极少的&#xff0c;不足以支撑分析的进行&#xff0c;这时就需要使用一些数学的方法&#xff0c;“模拟产生”一些…...

hive中struct相关函数总结

目录 hive官方函数解释示例实战 hive官方函数解释 hive官网函数大全地址&#xff1a;添加链接描述 Return TypeNameDescriptionstructstruct(val1, val2, val3, …)Creates a struct with the given field values. Struct field names will be col1, col2, …structnamed_str…...

macos下转换.dmg文件为 .iso .cdr文件的简单方法

为了让镜像文件在mac 和windows平台通用, 所以需要将.dmg格式的镜像文件转换为.iso文件, 转换方法也非常简单, 一行命令即可 hdiutil convert /path/to/example.dmg -format UDTO -o /path/to/example.iso 转换完成后的文件名称默认是 example.iso.cdr 这里直接将.cdr后缀删…...

ALSA学习(5)——设备中的alsa

参考博客&#xff1a; https://blog.csdn.net/DroidPhone/article/details/7165482 &#xff08;一下内容基本是原博主的博客转载&#xff09; 文章目录 一、ASOC的由来二、硬件架构三、软件架构四、数据结构五、内核对ASoC的改进 一、ASOC的由来 ASoC–ALSA System on Chip …...

uniapp中组件库的丰富NumberBox 步进器的用法

目录 基本使用 #步长设置 #限制输入范围 #限制只能输入整数 #禁用 #固定小数位数 #异步变更 #自定义颜色和大小 #自定义 slot API #Props #Events #Slots 基本使用 通过v-model绑定value初始值&#xff0c;此值是双向绑定的&#xff0c;无需在回调中将返回的数值重…...

【Matlab】基于遗传算法优化BP神经网络 (GA-BP)的数据时序预测

资源下载&#xff1a; https://download.csdn.net/download/vvoennvv/88682033 一&#xff0c;概述 基于遗传算法优化BP神经网络 (GA-BP) 的数据时序预测是一种常用的机器学习方法&#xff0c;用于预测时间序列数据的趋势和未来值。 在使用这种方法之前&#xff0c;需要将时间序…...

计算机毕业设计 基于HTML5+CSS3的在线英语阅读分级平台的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

云原生|kubernetes|kubernetes资源备份和集群迁移神器velero的部署和使用

前言&#xff1a; kubernetes集群需要灾备吗&#xff1f;kubernetes需要迁移吗&#xff1f; 答案肯定是需要的 那么&#xff0c;如何做kubernetes灾备和迁移呢&#xff1f;当然了&#xff0c;有很多的方法&#xff0c;例如&#xff0c;自己编写shell脚本&#xff0c;或者使用…...

【26.4K⭐】ShareX:一款开源免费、功能强大且丰富的截屏录屏软件

【26.4K⭐】ShareX&#xff1a;一款开源免费、功能强大且丰富的截屏录屏软件 在日常工作、学习和娱乐过程中&#xff0c;我们经常需要截取屏幕或者录制屏幕上特定区域中的内容并进行标记、编辑等操作。无论是为了记录重要的信息、分享有趣的内容&#xff0c;还是为了制作教程和…...

什么是ajax,为什么使用ajax?

概念&#xff1a;ajax是一种现有的技术集合&#xff0c;技术内容包括&#xff1a;HTML或XHTML&#xff0c;CSS&#xff0c;JavaScript&#xff0c;DOM,XML,XSLT,以及最重要的XMLHttpRequest。用于浏览器与服务器之间使用异步传输&#xff0c;做到局部请求以实现局部刷新。 作用…...

AI面板识别 - 华为OD统一考试

OD统一考试 (B卷) 分值: 100分 题解: Java / Python / C++ 题目描述 AI识别到面板上有N(1 ≤ N ≤ 100)个指示灯,灯大小一样,任意两个之间无重叠。 由于AI识别误差,每次别到的指示灯位置可能有差异,以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1,右下角x2…...

Linux之磁盘分区,挂载

Linux分区 分区介绍 对linux来说无论有几个分区&#xff0c;分给哪个目录使用&#xff0c;归根结底只有一个根目录&#xff0c;linux中每个分区都是用来组成整个文件系统的一部分。linux采用“载入"的处理方法&#xff0c;他的整个文件系统中包含一整套的文件和目录&…...

2核2G3M服务器上传速度多少?以阿里云和腾讯云为例

2核2G3M服务器上传速度多少&#xff1f;上传是按10M带宽算&#xff0c;上传速度是1280KB/秒&#xff0c;即1.25M/秒&#xff1b;下载速度按3M带宽计算&#xff0c;下载速度是384KB/秒。本文是以阿里云为例的&#xff0c;阿里云服务器当公网带宽小于10M及10M以下时&#xff0c;上…...

Cisco模拟器-OSPF路由协议

设计要求用两台双口路由器连接不同IP网段的计算机&#xff0c;并使用OSFP协议发现路由表使不同IP网段的计算机可以相互通信。 通过设计&#xff0c;可以连通IP地址网段不同的局域网&#xff0c;可应用在园区网的互连和互通的实现上。 主要配置步骤 路由器0&#xff1a; Router…...

SpEL 的使用

SpEL 的使用 SpEL的全称为 Spring Expression Language&#xff0c;具有再运行时构建复杂表达式、存取对象图属性、对象方法调用等功能 下面是一个简单样例 public class SpelTest { Test public void test1() { ExpressionParser parser new SpelExpressionParser(); …...

数据采集实战:电商详情页数据埋点

本文我们以电商产品的商品详情页为例&#xff0c;介绍如何做用户浏览以及点击行为的数据埋点。 案例中包含一个页面&#xff08;商品详情页&#xff09;以及该页面上的关键按钮&#xff08;加购、收藏按钮&#xff09;&#xff0c;具体页面如下图所示。 &#xff08;1&#xf…...

计算机网络——计算大题(七)

前言&#xff1a; 最近也是在准备计算机考试&#xff0c;我们的考试形式是上机考试&#xff0c;所以可能有些计算题是会给提供思路的&#xff0c;前面已经对本学期的计算机网络知识有了一个简单的认识与了解&#xff0c;现在我们就来对计算大题进行一个学习吧&#xff0c;这里的…...

子网掩码与IP段计算

一.什么叫子网掩码&#xff1a; 子网掩码(subnet mask)又叫网络掩码、地址掩码、子网络遮罩&#xff0c;它用来指明一个IP地址的哪些位标识的是主机所在的子网&#xff0c;以及哪些位标识的是主机的位掩码。子网掩码不能单独存在&#xff0c;它必须结合IP地址一起使用。 子网掩…...

【译文】IEEE白皮书 6G 太赫兹技术的基本原理 2023版

第一章 简介 太赫兹波是介于微波和光波之间的光谱区域&#xff0c;频率从 0.1THz ~ 10THz 之间&#xff0c;波长在 3mm ~ 30μm 之间。提供大块连续的频带范围以满足对 Tbit/s 内极高数据传输速率的需求&#xff0c;使该区域成为下一代无线通信&#xff08;6G&#xff09;的重…...

AUTOSAR从入门到精通-网络通信(UDPNm)(三)

目录 前言 原理 网络状态 初始化 执行 处理器架构 时间参数...

ubuntu 使用openssl制作一个自签名证书

我们需要为浏览器创建自己的根CA证书来信任自签名证书。因此&#xff0c;让我们首先创建根CA证书 创建根CA证书 创建文件夹 mkdir openssl && cd openssl执行以下openssl命令&#xff0c;生成 rootCA.key 以及 rootCA.crt. 用你的域名或者ip地址替换demo.mlopshub.c…...

WPF+Halcon 培训项目实战(1-5):Halcon安装,图像处理,Halcon简单模板匹配

文章目录 前言相关链接项目专栏我个人对就业市场的评价Halcon安装实战1-4&#xff1a;Halcon基础实战5&#xff1a;模板匹配[形状匹配]实战代码 结尾 前言 为了更好地去学习WPFHalcon&#xff0c;我决定去报个班学一下。原因无非是想换个工作。相关的教学视频来源于下方的Up主…...

虚函数的讲解

文章目录 虚函数的声明与定义代码演示基类Person派生类Man派生类Woman 测试代码动态绑定静态绑定访问私有虚函数总结一下通过成员函数指针调用函数的方式 虚函数的声明与定义 虚函数存在于C的类、结构体等中&#xff0c;不能存在于全局函数中&#xff0c;只能作为成员函数存在…...

Java强软弱虚引用

面试&#xff1a; 1.强引用&#xff0c;软引用&#xff0c;弱引用&#xff0c;虚引用分别是什么&#xff1f; 2.软引用和弱引用适用的场景&#xff1f; 3.你知道弱引用的话&#xff0c;能谈谈WeakHashMap吗&#xff1f; 目录 一、Java引用 1、强引用&#xff08;默认支持模式…...

QCharView使用

QCharView概念:title、系列、图标Chart、视图 说明: 需要添加Qt组件charts 在使用QChart或者QChartView之前需要添加宏定义QT_CHARTS_USE_NAMESPACE &#xff08;其实是使用了命名空间&#xff09;&#xff0c;不然不能识别QChart或者QChartView 3.在添加宏定义QT_CHARTS_USE_N…...

华为hcia之ipv6实验手册

R3: dhcp enable ipv6 dhcpv6 pool test address prefix 2000:23::/64 excluded-address 2000:23::2 dns-server 2000:23::2 interface GigabitEthernet0/0/0 ipv6 enable ipv6 address 2000:12::2/64 ipv6 address auto link-local undo ipv6 nd ra halt //无状态配置 inter…...

算法设计与分析-图算法小结BFS/DFS/Topologic/Dijkstra/Floyd/最大流

图 注:CSDN貌似不支持较长公式&#xff0c;可以复制到Markdown编辑器查看 图的表示 邻接矩阵 空间复杂度 Θ ( V 2 ) Θ(V^2) Θ(V2)邻接链表 空间复杂度 Θ ( V E ) Θ(VE) Θ(VE) BFS 邻接链表 时间复杂度 Θ ( V E ) Θ(VE) Θ(VE) void BFS(Graph G, int v) {//…...

CentOS 8 安装指定版本ansible

背景&#xff1a;想要练习ansible使用&#xff0c;用于面试&#xff0c;结果使用centos 8 的yum安装失败&#xff0c;提示版本不兼容&#xff08;指的是python版本&#xff09;&#xff0c;故而使用python来安装指定版本的ansible&#xff0c;特此记录 环境&#xff1a;win11虚…...