Ref: link

343. Integer Break (Medium)

This problem is not easy, because we cannot ensure how many integers we can break n into. The solution is we break n into 2 numbers or iterate dp to find the better way. dp[i] means the maximum product we can get for value i, so the length of dp array is n+1. And all initial values should be 1, because the answer of value 2 should be 1(1*1=1). And other answers should be larger than 1. Then, we iterate all numbers j which are smaller than n. If we break n into two numbers, these two numbers should be j and (i-j). If we break n into more numbers, we need to check previous dp elements. dp[i-j]*j. dp[i-j] means the maximum product we can get for value i-j. Therefore, the dp formula is dp[i] = Math.max(dp[i-j]*j,((i-j)*j)).

The time complexity of my dp solution is O(n^2). But we have better solutions. Space complexity is O(n). If we can use some math tricks, we can reduce time complexity and space complexity. Here is the link.

public int integerBreak(int n) {
    int []dp = new int[n+1];
    for(int i =0;i<n+1;i++)dp[i]=1;
    for(int i = 3;i<n+1;i++){
        for(int j = 1;j<i;j++){
            dp[i] = Math.max(dp[i],Math.max(dp[i-j]*j,j*(i-j)));
        }
    }
    return dp[n];
}

279. Perfect Squares(Medium)

The solution to this problem is similar to the last problem. In the last problem, we break n into some integers. In this problem, we break integer n into some square integers. We still use dp to solve this problem. dp[i] means the least number of perfect square numbers. At first, we need to initialize all values to Integer.MAX_VALUE, because we need to find the least numbers. Then, we don’t assign values one by one. At first, we assign all square numbers. And then assign all remaining values. dp formula is dp[i+jj] = Math.min(dp[i+jj],dp[i]+1).

Time complexity is O(n^2). Space complexity is O(n). We can reduce time and space complexity by using some math solution. Here is the link.

public int numSquares(int n) {
    int[]dp = new int[n+1];
    for(int i =0;i<n+1;i++)dp[i]=Integer.MAX_VALUE;
    dp[0]=0;
    for(int i =0;i<n+1;i++){
        for(int j=1;i+j*j<n+1;j++){
            dp[i+j*j] =Math.min(dp[i+j*j], dp[i]+1);
        }
    }
    return dp[n];
}