怎么做关于狗的网站,国外做农产品有名的网站,微信搜索seo优化,前端做网站是什么流程目录
力扣279. 完全平方数
问题解析
解析代码
优化代码#xff08;相同子问题分析和滚动数组#xff09; 力扣279. 完全平方数
279. 完全平方数
难度 中等
给你一个整数 n #xff0c;返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数#xff0c;其值…目录
力扣279. 完全平方数
问题解析
解析代码
优化代码相同子问题分析和滚动数组 力扣279. 完全平方数
279. 完全平方数
难度 中等
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12输出3
解释12 4 4 4
示例 2
输入n 13输出2
解释13 4 9
提示
1 n 10^4
class Solution {
public:int numSquares(int n) {}
}; 问题解析
优化代码部分放了分析一维空间的思路这个普通思路就简单描述了
状态表示 dp[i][j] 表示从前i个完全平方数中挑选总和正好等于j所有选法中最小的数量。
状态转移方程 线性 dp 状态转移方程分析方式一般都是根据最后一步的状况来分情况讨论。但是最后一个物品能选很多个因此需要分很多情况
选 0 个i * idp[i][j] dp[i - 1][j] 选 1 个i * idp[i][j] dp[i - 1][j - i * i] 1 ;选 2 个i * idp[i][j] dp[i - 1][j - 2 * i * i] 2 ;......
综上状态转移方程为
dp[i][j] min(dp[i - 1][j] , dp[i - 1][j - i * i] 1 dp[i - 1][j - 2 * i * i] 2 , ......) 这时发现计算一个状态的时候需要一个循环才能搞定的时候我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态通常就是用数学的方式做一下等价替换。 发现第二维是有规律的变化的因此去看看 dp[i][j - i * i] 1 ; 这个状态 dp[i][j - i * i] 1 min( dp[i - 1][j - 2 * i * i] 2 , dp[i - 1][j - 3 * i * i] 3 , ......) 因此可以修改我们的状态转移方程为 dp[i][j] min(dp[i - 1][j] , dp[i][j - i * i] 1。j i * i 。有个技巧就是相当于把第二种情况 dp[i - 1][j - i * i] 1 里面的 i - 1 变成 i 即可。
初始化 初始化第一行即可dp[0[0]为1第一行后面初始化成无穷大。
填表顺序 根据状态转移方程仅需从上往下填表。
返回值 根据状态表示返回 dp[根号n][n] 。 解析代码
class Solution {
public:int change(int amount, vectorint coins) {int n coins.size();vectorint dp(amount 1, 0); // 滚动数组优化dp[0] 1;for(int i 1; i n; i){for(int j coins[i - 1]; j amount; j){dp[j] dp[j] dp[j - coins[i - 1]];}}return dp[amount];}
}; 优化代码相同子问题分析和滚动数组 先看能不能将问题转化成我们熟悉的题型。这里给出一个用拆分出相同子问题的方式定义一个状态表示。得到的结果 i 和 j 换一下就是滚动数组优化的结果
为了叙述方便把和为 n 的完全平方数的最少数量简称为最小数量。
对于 12 这个数分析一下如何求它的最小数量。
如果 12 本身就是完全平方数就不用算了直接返回 1 ;但是 12 不是完全平方数试着把问题分解⼀下
情况一拆出来一个 1 然后看看 11 的最小数量记为 x1 情况二拆出来一个 4 然后看看 8 的最小数量记为 x2 为什么拆出来 4 而不拆出来 2 呢情况三拆出来一个 8 ...... 其中接下来求 11、8 的时候其实又回到了原来的问题上。 因此可以尝试用 dp 的策略将 1 2 3 4 6 等等这些数的最小数量依次保存起来。再求较大的 n 的时候直接查表然后找出最小数量。
状态表示 dp[i] 表示和为 i 的完全平方数的最少数量。
状态转移方程 对于 dp[i] 根据思路里的分析知道可以根据小于等于 i 的所有完全平方数 x 进行划分
x 1 时最小数量为 1 dp[i - 1] x 4 时最小数量为 1 dp[i - 4] ......
为了方便枚举完全平方数采用的策略 for(int j 1; j * j i; j)
综上状态转移方程为
dp[i] min(dp[i], dp[i - j * j] 1)
初始化当 n 0 的时候没法拆分结果为 0 当 n 1 的时候结果为 1 。
填表顺序 根据状态转移方程仅需从左往右填表。
返回值 根据状态表示返回 dp[n] 。
class Solution {
public:int numSquares(int n) {// dp[i] 表示和为 i 的完全平方数的最少数量int m sqrt(n);vectorint dp(n 1, 0x3f3f3f3f);dp[0] 0;for(int i 1; i m; i){for(int j i * i; j n; j){dp[j] min(dp[j], dp[j - i * i] 1);}}return dp[n];}
};
