leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决

柔情只为你懂 2022-06-08 14:12 171阅读 0赞

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

动态规划用 dp\[i\] 数组存储第 i 个数的完美平方数。递推式为：

dp[i] = Math.min(dp[j] + dp[i-j], dp[i])

这里认为 i 的完全平方数是从和为 i 的两个完全平方数 dp\[j\] 和 dp\[i-j\]之和，然后从中取最小，不过这里的j就是i\*i，红色部分表示平方数，所有的数都可以看做一个普通数加上一个完美平方数，那么递推式就变为了：

dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])

建议和这一道题[leetcode 518. Coin Change 2 动态规划DP][leetcode 518. Coin Change 2 _DP] 和 [leetcode 322. Coin Change 类似背包问题 + 很简单的动态规划DP解决][leetcode 322. Coin Change _ _ _DP] 和[leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS][leetcode 416. Partition Equal Subset Sum _DP _ _DFS]一起学习

还有 [leetcode 494. Target Sum目标和 + 背包问题 + 深度优先遍历DFS + 动态规划DP + 简单的分析推导 ][leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]

代码如下：

import java.util.Arrays;
    
    /*
     * 使用DP来计算
     * http://www.cnblogs.com/liujinhong/p/6022546.html
     * 红色部分表示平方数，所有的数都可以看做一个普通数加上一个完美平方数，
     * 那么递推式就变为了：dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])。
     * */
    class Solution 
    {
        public int numSquares(int n) 
        {
            if(n<=0)
                return 0;
            //dp[i]表示容量为i的完美次数
            int[] dp=new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0]=0;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=i;j++)
                {
                    if(j*j>i)
                        break;
                    else
                        dp[i]=Math.min(dp[i], dp[i-j*j]+1);
                }
            }
            return dp[n];
        }
    }

下面是C++的做法，一个很不错的DP动态规划的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    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];
        }
    };

[leetcode 518. Coin Change 2 _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 322. Coin Change _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78150520
[leetcode 416. Partition Equal Subset Sum _DP _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78752598
[leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]: http://blog.csdn.net/jackzhang_123/article/details/78793365