面试华为遇到了经典动态规划题 - 怎么用go、C++进行编程解决

华为的知名很大程度上源自于在经历过被美国的制裁和打压后不仅撑住了，而且还做出了相对于自己来说技术进步程度很大的芯片​。这是一个不小的成绩​。

从个人的角度上来说，华为是最难进的一家大公司之一，它的面试标准很严格​。这不仅是筛选人才，在某种程度上来说也是由于求职市场的饱和而导致的​，因为以前求职华为的难度要比现在低很多。

伴随着相对于某些企业来说更大的工作压力下，华为能给出的工资待遇要远超绝大多数的公司​。这也是面试求职华为竞争激烈的重要原因之一​。

今天带来一道​在华为面试中出现过的题目。

题目描述：

题号：279

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

解题思路：

思路一：动态规划

它的关键在于找出状态转移方程和边界条件：

状态转移方程：

边界条件：

• dp[0] = 0（0 的平方等于 0）。

时间复杂度：O(N * sqrtN) 

空间复杂度：O(N)

C++

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

go

// go
func numSquares(n int) int {  
    dp := make([]int, n+1)  
    for i := 1; i <= n; i++ {  
        dp[i] = math.MaxInt32  
        for j := 1; j*j <= i; j++ {  
            dp[i] = min(dp[i], dp[i-j*j]+1)  
        }  
    }  
    return dp[n]  
}  
  
func min(a, b int) int {  
    if a < b {  
        return a  
    }  
    return b  
}