LeetCode June Challenge - Day 27

Problem: LeetCode June Challenge - Day 27

Ideas

  1. Standard knapsack problem.

Solution:

const int INF = 1000000000;
class Solution {
    int integer_root(int x){
        int lo=0, hi=10000;
        while(lo <= hi){
            int m = (lo+hi)/2;
            if(m*m <= x) lo = m+1;
            else hi = m-1;
        }
        return hi;
    }
public:
    int numSquares(int n) {
        int m = integer_root(n);
        int dp[n+1][m+1];
        for(int i=1; i <= n; ++i) dp[i][0] = INF;
        for(int i=0; i <= m; ++i) dp[0][i] = 0;
        for(int i=1; i <= n; ++i)
            for(int j=1; j<=m; ++j){
                dp[i][j] = dp[i][j-1];
                if(i >= j*j)
                    dp[i][j] = min(dp[i][j], 1+dp[i-j*j][j]);
            }
        return dp[n][m];
    }
};