[leetcode]动态规划之PerfectSquare

客官°小女子只卖身不卖艺 2021-09-29 02:10 279阅读 0赞

### 动态规划之PerfectSquare ###

*  题目
 *  思考
 *  代码
 *   *  数学方法
     *  动态规划

# 题目 #

[leetcode题目入口][leetcode]

# 思考 #

数学定理：四平方和定理：每个正整数均可表示为不超过4个完全平方数的和。  
**注意有些整数不可表示为3个完全平方数的和，例如7**

# 代码 #

## 数学方法 ##

class Solution { 
    public:
        int numSquares(int n) { 
        	//因为假如 c=a^2+b^2
        	//那么 4c=(2a)^2+(2b)^2同样也是2个数组成
            while(n % 4 == 0) {  
                n /= 4;
            }
            if(n % 8 == 7) {  
                return 4;
            }
            for(int a = 0; a * a <= n; ++a) { 
                int b = sqrt(n - a * a);
                if(a * a + b * b == n) {  
                    return !!a + !!b; 
                }
            }
            return 3;
        }
    };

## 动态规划 ##

class Solution { 
    public:
        int numSquares(int n) { 
            vector<int> dp(n + 1, INT_MAX);
            dp[0] = 0;
            for(int i = 0; i <= n; ++i){ 
                for(int j = 1; i + j * j <= n; ++j){ 
                    dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
                }
            }
            return dp.back();
        }
    };

[leetcode]: https://leetcode.com/problems/perfect-squares/submissions/

发表评论取消回复

表情：

评论列表（有 0 条评论，279人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode高级算法之动态规划

[152. Maximum Product Subarray][] 这题与最大子序列和不同的地方在于, 乘积的状态转移不能用dp\[i-1\]\num\[i\]来获得, 因为

深藏阁楼爱情的钟/ 2022年12月28日 04:04/ 0 赞/ 112 阅读

相关 leetcode动态规划

1. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？动态规划模板题，思考方法，1个台

布满荆棘的人生/ 2022年09月05日 04:07/ 0 赞/ 147 阅读

相关 [leetcode]动态规划之PerfectSquare

动态规划之PerfectSquare 题目思考代码数学方法动态规划题目 [leetcode题目入口][lee

客官°小女子只卖身不卖艺/ 2021年09月29日 02:10/ 0 赞/ 280 阅读

相关 [leetcode]动态规划之Ugly Number

动态规划之Ugly Number 题目思考代码题目 [leetcode入口][leetcode] 思考这是一道结合了数学的dp题

秒速五厘米/ 2021年09月29日 01:52/ 0 赞/ 280 阅读

相关 [leetcode]动态规划之CountingBits

动态规划之CountingBits 题目思考代码题目 [leetcode入口][leetcode] 思考这道题让我思考了dp数组

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 273 阅读

相关 [leetcode]动态规划之Maximal Square

动态规划之Maximal Square 题目思考代码题目 [leetcode入口][leetcode] 思考之前认为dp表格的含

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 301 阅读

相关 [leetcode]动态规划之House Robber II

动态规划之House Robber II 题目思考代码题目 [leetcode入口][leetcode] 思考刚开始想的dp\[

╰+攻爆jí腚メ/ 2021年09月29日 01:14/ 0 赞/ 227 阅读

相关 [leetcode]动态规划之Maximum Product Subarray

动态规划之Maximum Product Subarray 题目思考类型归类代码题目 [leetcode入口][leetcode]

女爷i/ 2021年09月28日 14:52/ 0 赞/ 273 阅读

相关 [leetcode]动态规划之wordbreak

动态规划之wordbreak 题目知识点思考代码题目 [leetcode入口][leetcode] 知识点 unorder

短命女/ 2021年09月28日 14:48/ 0 赞/ 303 阅读

相关 [leetcode]动态规划之Triangle

动态规划之Triangle 题目思考答案题目 [leetcode入口][leetcode] 思考刚开始想这道题，想着的是建立一维

缺乏、安全感/ 2021年09月28日 14:46/ 0 赞/ 445 阅读