Leetcode 279. Perfect Squares 经典一维动态规划问题

题目表述

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

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

一维动态规划

本题是一个经典的一维动态规划问题，也是最为简单的一类动态规划问题。从本质上而言，动态规划 和 回溯逆推算法， 这两种算法是一体两面，并且在大部分问题中可以相互替换。

一般而言，动态规划是从最简单的情况出发，推论到复杂的情况，比如一维动态规划一般是从 dp[0] 推论到 dp[n], 并且最终得到结果。由于计算过程中不断可以复用到之前的结果，所以动态规划一般所有额外空间较少，效率较高；但是递推关系式往往不够明确。

而回溯逆推方法，则是从目标情况出发，逆推到最简单的情况，比如一维的回溯一般是从 func(n) 出发回溯到 func(0)。一般回溯法需要通过一个hashmap保存中间结果，用于复用，所以使用了较多的额外空间，效率较低。但是写回溯就如同从外向内剥洋葱，因而更加容易掌握规律；而动态规划就如同把洋葱一瓣一瓣重新拼起来，不太直观。

动态规划 (>50.43%)

class Solution {
    public int numSquares(int n) {

        if (n==1) return 1;
        if (n==2) return 2;
        int[] nums = new int[n+1];
        nums[1] = 1;
        nums[2] = 2;

        for (int i=0;i*i<=n;i++){
            nums[i*i] = 1;
        }

        for (int i=1;i<=n;i++){
            for (int j=1;i+j*j<=n;j++){
                if (nums[i]+1<nums[i+j*j] || nums[i+j*j]==0) nums[i+j*j]=nums[i]+1;
            }
            //System.out.printf("nums[%d]=%d\n",i,min);
        }
        return nums[n];
    }
}