算法

发布日期: 2024-03-07

更新日期: 2024-03-19

文章字数: 2k

阅读时长: 8 分

阅读次数:

想必提到动态规划大家都很头痛，本人也是。最近在leetcode上刷了一个动态规划的题目最长有效括号，通过学习题解中的动态规划解法对动态规划有了一些理解，并且看到了参考文档【1】，又有了一些理解，于是整理出本文，写出自己对动态规划的理解，希望对大家理解动态规划有帮助。

一句话理解

记住之前的计算结果以供后续计算使用

我的理解

我理解，动态规划和递归非常类似，都是把大问题拆解成小问题。总结成公式为：

大问题=小问题+一个操作

小问题=边界问题

动态规划就是把大问题一层一层拆解成：小问题+一个操作，并且记录每一层的结果。小问题最后通过边界问题得到解决。

通过简单示例理解

问题：假设有最够多的1，问需要多少个1相加才能得到5

问题很傻逼，但有助于我们理解动态规划。

第一步：大问题=小问题+一个操作

多少个1相加才能得到5=多少个1相加才能得到4+一个操作（加一个1），如果定义一个数组dp，下标idx表示需要得到的数，dp[idx]表示得到idx需要的1的个数，则dp[5]=dp[4]+1

继续拆解子问题：多少个1相加才能得到4

显然，多少个1相加才能得到4=多少个1相加才能得到3+一个操作（加一个1），则dp[4]=dp[3]+1

以此类推，dp[3]=dp[2]+1,dp[2]=dp[1]+1

第二步：小问题=边界问题

dp[1]:表示多少个1相加才能得到1，显然dp[1]=1

因此，dp[2]=dp[1]+1=2,dp[3]=dp[2]+1=3,dp[4]=dp[3]+1=4,dp[5]=dp[4]+|1=5,至此我们得到答案是5

标准思路

通过上面简单示例，我们看到，动态规划就是把大问题分解成小问题+一个操作，并且用一个数组记录每个小问题的结果，到问题拆解得足够小、不可再拆的时候，就是边界问题了，就很好解决了。

动态是什么意思

动态就是把大问题拆解成小问题+一个操作，这个拆解的过程就叫做动态

规划是什么意思

规划就是把小问题的边界条件找出来，这个边界条件就叫做规划，意思是划定这个小问题的界限，这样就能求解这个小问题

示例1：最长有效括号

题目：给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0

问题分析：拿到这个问题，如果告诉你要用动态规划，该怎么思考？

第一步：定义一个数组dp，dp[i]表示以第i个括号结尾的最长有效括号的长度

第二步：两步骤。

1.大问题=小问题+一个操作

2.小问题=边界问题

我们先把框架搭在这里，然后来思考。如何将大问题转换成小问题+一个操作呢？显然按照公式可以得到：dp[i]=dp[i-1]+一个操作。这样就把大问题dp[i]转换成了小问题dp[i-1]。

那么如何确定”一个操作“呢？假设i为数组中的某个元素，则肯定需要分析一下输入字符串s的第i个字符的值。

当s[i]=”(“，显然最长有效括号字符串的结尾不可能是”(“，因此直接得到dp[i]=0,这个时候就不需要用到公式dp[i]=dp[i-1]+一个操作了。
当s[i]=”)”,则往前找到与s[i]能匹配上的字符
- 当s[i-1]=”(“，则s[i]只能与s[i-1]匹配，dp[i]等于dp[i-2]位置的值再加2个字符。即dp[i]=dp[i-2]+2
- 当s[i-1]=”)”, 则找到以s[i-1]结尾的最长有效括号的第一个字符下标x=i-dp[i-1]，
- - 如果s[x-1]=”(“，则刚好与s[i]匹配，则dp[i]=dp[x-2]+dp[i-1]+2

如果s[x-1]=”)”, 则s[i]找不到匹配的字符，则dp[i]=0
大问题拆解成小问题+一个操作已经分析完了，现在来分析小问题=边界问题。边界问题最容易，我们只需要枚举出几种情况即可。如当i=0,1,2,3，dp[i]应该等于多少。本题的边界问题就是i,i-1,x,x-1小于0的情况，当小于0说明没有找到与s[i]相匹配的字符，直接赋值dp[i]=0即可。

代码如下：

const (
	LeftKuohao = '('
	RightKuohao = ')'
)

func LongestValidParentheses(s string) int {
	dp := make([]int,len(s))
	max := 0
	for i:=range s{
		if s[i]==LeftKuohao{
			dp[i]=0
		}else{
			if i==0{
				return 0
			}
			if s[i-1]==LeftKuohao{
				if i-2<0{
					dp[i]=2
				}else{
					dp[i]=dp[i-2]+2
				}
			}else {
				idx := i-1-dp[i-1]
				if idx>=0{
					if s[idx]==LeftKuohao{
						dp[i]=dp[i-1]+2+dp[idx-1]
					}
				}
			}
			if dp[i]>max{
				max=dp[i]
			}
		}
	}
	return max
}

示例2：322.零钱兑换

题目（对leetcode有改版）：你有三种硬币，2元、5元、7元，每种硬币足够多，买一本书需要27元，用最少的硬币组合

问题分析：拿到这个问题，如果告诉你要用动态规划，该怎么思考？

第一步：定义一个数组dp，dp[i]表示凑齐i元需要的最少硬币数量

第二步：两步骤。

1.大问题=小问题+一个操作

2.小问题=边界问题

如何凑齐27元呢？27=25+2，22+5，20+7，因此dp[27]=min(dp[25]+1,dp[22]+1,dp[20]+1), 公式为：dp[i]=min(dp[i-2]+1,dp[i-5]+1,dp[i-7]+1)。第一步轻轻松松解决。这里的小问题+一个操作与之前有一点不一样，小问题等于多个小问题取最小值

小问题的边界问题是什么？枚举

当dp[i]=正无穷大，则表示没有硬币组合能得到i，则dp[0]=0,dp[1]=正无穷大,dp[2]=1,dp[3]=正无穷大。

归总为:

当i<0, dp[i]=正无穷大

当i=0, dp[0]=0
代码如下：

const (
	MaxNumber = 10000000000000000
)

func LessMoney(price int) int {
	dp := make([]int, price+1)
	dp[0] = 0
	for i:=1;i<= price;i++ {
		min := MaxNumber
		if i-2>=0{
			if dp[i-2]+1<min{
				min=dp[i-2]+1
			}
		}
		if i-5>=0{
			if dp[i-5]+1<min{
				min=dp[i-5]+1
			}
		}
		if i-7>=0{
			if dp[i-7]+1<min{
				min=dp[i-7]+1
			}
		}
		dp[i] = min
	}
	return dp[price]
}

扩展：如果零币是任意输入，总价也是任意输入呢？即leetcode的322题目，代码如下：

const (
	MaxNumber = 10000000000000000
)

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
	dp[0] = 0
	for i:=1;i<= amount;i++ {
		min := MaxNumber
		for j:=range coins{
			if i-coins[j]>=0{
				if dp[i-coins[j]] < min {
					min = dp[i-coins[j]]+1
				}
			}
		}
		dp[i] = min
	}
	if dp[amount] == MaxNumber {
        return -1
    }
    return dp[amount]
}

本文用了三个示例解释了该如何做动态规则的算法题，再次回顾一下。

第一步：大问题=小问题+一个操作

第二步：小问题=边界问题

这两步看起来容易，真正能想出来如何拆分也不是那么容易，需要平时多做一些算法题，尤其是动态规划类的题目，结合上面两步骤，多想一想为什么这个题可以这样拆分。更多的动态规划的题目可见参考文档【1】，有想法或者疑问欢迎在评论区探讨，共同学习。