代码随想录算法训练营第三十七天 | leetcode：零钱兑换,完全平方数
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
322. 零钱兑换
解题方法
思路：与之前完全背包题型不同，这又算是一种新的题型，求解装满背包的最少物品数。之前的题型是，装满背包的最大价值，装满背包有多少种方式。
- dp数组的含义：dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
- 确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
- dp[j - coins[i]] + 1：表示放入coins[i]时，物品的数量。
- dp[j]：表示没放入coins[i]时，物品的数量。
- 初始化dp数组：除了dp[0]=0,其余都初始化为PHP_INT_MAX。因为递推公式需要求得较小值。
- 遍历顺序：外层为物品（从小到大），内层为背包（从小到大）。
code
class Solution {
/**
* @param Integer[] $coins
* @param Integer $amount
* @return Integer
*/
function coinChange($coins, $amount) {
$dp = [];
$len = count($coins);
//初始化dp数组为最大int值，方便后续求较小值
for($i = 0; $i <= $amount; $i++){
$dp[$i] = PHP_INT_MAX;
}
$dp[0] = 0;
for($i = 0; $i < $len; $i++){
for($j = $coins[$i]; $j <= $amount; $j++){
// 如果dp[j - coins[i]]是PHP_INT_MAX则跳过,表示当前组合组成不了dp[j]
if ($dp[$j - $coins[$i]] != PHP_INT_MAX) {
$dp[$j] = min($dp[$j], $dp[$j-$coins[$i]] + 1);
}
}
}
//print_r($dp);
if($dp[$amount] == PHP_INT_MAX) return -1;
return $dp[$amount];
}
}复杂度
时间复杂度
O(n * amount)，其中 n 为 coins 的长度
空间复杂度
O(amount)
279. 完全平方数
解题方法
思路：与上题相同，都是求装满背包最小物品数，只是这道题没有给出物品数组，需要自己构造nums物品数组。
- dp数组的含义：dp[j]：和为j的完全平方数的最少数量为dp[j]
- 确定递推公式：dp[j] = min(dp[j], dp[j-nums[i] + 1]);
- 初始化dp数组：除了dp[1]=1,其余都初始化为PHP_INT_MAX。
- 遍历顺序：外层为物品（从小到大），内层为背包（从小到大）。
code
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function numSquares($n) {
//构建nums物品数组
$nums = range(1, sqrt($n) + 1);
foreach ($nums as $key => $val){
$nums[$key] = $val * $val;
}
//print_r($nums);
$dp = [];
//初始化dp数组
for ($i = 1; $i <= $n; $i++) {
$dp[$i] = PHP_INT_MAX;
}
$dp[1] = 1;
//遍历物品与背包
for ($i = 1; $i < count($nums); $i++) {
for ($j = $nums[$i]; $j <= $n; $j++) {
$dp[$j] = min($dp[$j], $dp[$j - $nums[$i]] + 1);
}
}
//print_r($dp);
return $dp[$n];
}
}简化版
class Solution {
/**
* @param Integer $n
* @return Integer
*/
function numSquares($n) {
for ($i = 1; $i <= $n; $i++) $dp[$i] = PHP_INT_MAX;
$dp[1] = 1;
//遍历时使用i*i表示nums物品数组，节省空间
for ($i = 1; $i * $i <= $n; $i++) {
for ($j = $i * $i; $j <= $n; $j++) $dp[$j] = min($dp[$j], $dp[$j - $i * $i] + 1);
}
return $dp[$n];
}
}数学证明解法（时间复杂度最低）
class Solution {
/**
* @param Integer $n
* @return Integer
*/
/**
思路：这里运用到四平方和定理的推论
若n=4^k*(8m+7)，则个数为4，可以通过整除后 取余只 判断,
若n本身等于一个数的平方，则无可厚非个数为1;
若n等于一个数的平方加剩余数的平方，则个数为2;
以上都不是则返回3.
*/
function numSquares($n) {
if($this->isPerfectSquare($n)){
return 1;
}
for($i=1;$i*$i<$n;$i++){
if($this->isPerfectSquare($n-$i*$i)){
return 2;
}
}
if($this->checkAnswer4($n)){
return 4;
}
return 3;
}
function checkAnswer4($n){
while($n%4==0){
$n/=4;
}
return $n%8==7;
}
function isPerfectSquare($n){
$x=sqrt($n);
return $x==intval($x);
}
}复杂度
时间复杂度
O(n * √n)
空间复杂度
O(n)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号