LeetCode 279. 完全平方数C#
原题链接
中等
作者:
hpstory
,
2022-09-22 21:59:51
,
所有人可见
,
阅读 161
C# 二维DP 代码
public class Solution {
public int NumSquares(int n) {
List<int> nums = new List<int>();
for (int i = 1; i * i <= n; i++){
nums.Add(i * i);
}
int m = nums.Count;
int[,] dp = new int[m + 1, n + 1];
for (int j = 1; j <= n; j++) dp[0, j] = 10000;
for (int i = 1; i <= m; i++){
for (int j = 0; j <= n; j++){
dp[i, j] = dp[i - 1, j];
if (j >= nums[i - 1]){
dp[i, j] = Math.Min(dp[i, j], dp[i, j - nums[i - 1]] + 1);
}
}
}
return dp[m, n];
}
}
C# 一维DP 代码
public class Solution {
public int NumSquares(int n) {
List<int> nums = new List<int>();
for (int i = 1; i * i <= n; i++){
nums.Add(i * i);
}
int m = nums.Count;
int[] dp = new int[n + 1];
for (int j = 1; j <= n; j++) dp[j] = 10000;
for (int i = 1; i <= m; i++){
for (int j = nums[i - 1]; j <= n; j++){
dp[j] = Math.Min(dp[j], dp[j - nums[i - 1]] + 1);
}
}
return dp[n];
}
}