[数据结构与算法]动态规划之完全背包问题

日拱一卒，功不唐捐。

Leecode279完全平方数

题目大意
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

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

class Solution {
public:
    int numSquares(int n) {
//自己构造物品给背包
vector<int>nums;
for(int i=1;i<=sqrt(n);i++)nums.push_back(i*i);
    int size = nums.size();
    //由于是要根据dp关系求的最小值，所以应保证未更新的dp值够大，以用于更新最小值
    int dp[size+1][n+1];memset(dp,0x3f,sizeof(dp));
    //很明显base case是dp[..][0]无论前面的物品用与不用，构成容量为0的背包的所用个数只能是0
    //而dp[0][..]则明显是无法拼凑成任何数的，故只需要它为默认值就好
    for(int i=0;i<=size;i++)dp[i][0] = 0;
    //开始更新dp数组
    for(int i=1;i<=size;i++){
        for(int j=1;j<=n;j++){
            if(j>=nums[i-1])
            dp[i][j] = min(dp[i-1][j],dp[i][j-nums[i-1]]+1);
            else
            dp[i][j] = dp[i-1][j];
        }
    }
    return dp[size][n];
    }
};

想法
这两天做的题目都是构建二维dp数组，初读题目时找不到索引范围，后来看了题解发现他们巧妙的自己构建一个索引数组。
悟：有时没有路时可以给自己构建一条路。