题目链接：完全平方数

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

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

方法一：动态规划

class Solution {
public:
    int numSquares(int n) {
        int f[10010];
        //f[0] = 0;
        for (int i = 1;i <= n;i++) {
            f[i] = i;
            for (int j = 1;j * j <= i;j++) {
                f[i] = min(f[i],f[i-j*j]+1);
            }
           // f[i] = minn + 1;
        }
        return f[n];
    }
};

题目链接：最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

方法一：动态规划

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int f[2550];
        f[0] = 1;
        int ans = 1;
        for (int i = 1;i < nums.size();i++) {
            f[i] = 1;
            for (int j = 0;j < i;j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i],f[j] + 1);
                    ans = max(ans,f[i]);
                }
            }
        }
        return ans;
    }
};

方法二：贪心+二分

int first_ge(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size(); // [l, r)
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) r = m;
        else l = m + 1;
    }
    return l; // 第一个 >= x 的位置（可能等于 a.size()）
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        int i = first_ge(tails, x);
        if (i == (int)tails.size()) tails.push_back(x);
        else tails[i] = x;
    }
    return (int)tails.size();
}

题目链接：乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

方法一：动态规划

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int u_nums[20010];
        int d_nums[20010];
        u_nums[0] = nums[0] > 0 ? nums[0] : 1;
        d_nums[0] = nums[0] < 0 ? nums[0] : 0;
        int ans = nums[0];
        for (int i = 1;i < nums.size();i++) {
            if (nums[i] >= 0) {
                ans = max(ans,u_nums[i-1] * nums[i]);
                u_nums[i] = max(u_nums[i-1] * nums[i],1);
                d_nums[i] = d_nums[i-1] * nums[i];
            }else {
                ans = max(ans,d_nums[i-1] * nums[i]);
                u_nums[i] = max(d_nums[i-1] * nums[i],1);
                d_nums[i] = u_nums[i-1] * nums[i];
            }
        }
        return ans;
    }
};

题目链接：只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

方法一：异或

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto t : nums) ans ^= t;
        return ans;
    }
};

题目链接：零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

方法一：动态规划 + 二维数组

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector f(n + 1, vector<int>(amount + 1, INT_MAX / 2));
        f[0][0] = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j <= amount;j++) {
                if (j < coins[i]) {
                    f[i+1][j] = f[i][j];
                }else {
                    f[i+1][j] = min(f[i][j],f[i+1][j-coins[i]] + 1);
                }
            }
        }
        int ans = f[n][amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};

方法二：动态规划+一维数组

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INT_MAX / 2);
        f[0] = 0;
        for (int x : coins) {
            for (int i = x;i <= amount;i++) {
                f[i] = min(f[i],f[i-x] + 1);
            }
        }
        int ans = f[amount];
        return ans < INT_MAX / 2 ? ans : -1;
    }
};