leetcode_day41
本文最后更新于 2024年7月6日 晚上
今日内容:
- 322. 零钱兑换 medium
- 279. 完全平方数 medium
- 139. 单词拆分 medium
322. 零钱兑换
题目:
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数
。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
思路:
完全背包,dp[j]含义为凑成j需要的最少硬币个数,状态转移方程为:
\[ dp[j]\ = \begin{cases} 0, & \text{$j\ =\ 0$} \\ min(dp[j\ -\ coin[i]] + 1, dp[j]), & \text{else} \end{cases} \]
代码
1 |
|
279. 完全平方数
题目:
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
思路:
其实一开始考虑了数学,但只是记得有相关的数论结论,忘了具体内容,于是果断采用程序员做法————直接dp,很明显的完全背包,只是要求最少数量,把dp含义改一下就好,同时也要根据新的状态转移方程决定新的初始化方式。
dp[j]表示整数j需要的完全平方数的最少数量
状态转移方程为:
\[ dp[j]\ = \begin{cases} 0, & \text{$j\ =\ 0$} \\ min(dp[j], dp[j - i*i] + 1), & \text{$j\ ≥\ i^2, i\ =\ 1,2,3,……$} \\ \end{cases} \]
代码
1 |
|
139. 单词拆分
题目:
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
思路:
把s看成要填满的背包,从dict里一个一个试着装,这时候就不能太死板,要灵活迁移dp的含义:
dp[j]表示区间[0, j)的s能不能被表示
那么状态转移方程为:
\[ dp[j] = \begin{cases} true, & \text{$j = 0$} \\ dp[j]\ OR\ (dp[j - wordDict[i].size()]\ AND\ s(j\ -\ wordDict[i].size())\ ==\ wordDict[i]), & \text{else} \end{cases} \]
- 还要想到:这里必须先遍历背包容量再遍历字典,不然无法实现拼接,而是一直在判断s的开头。
- 还可以对字典去去重
代码
1 |
|