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

给你一个整数数组 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;
    }
};

题目链接：零钱兑换

给你一个整数数组 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;
    }
};

题目链接：打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

方法一：动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        int f[110];
        f[0] = nums[0];
        if (nums.size() == 1) return f[0];
        f[1] = max(nums[0],nums[1]);
        for (int i = 2;i < nums.size();i++) {
            f[i] = max(f[i-1],nums[i] + f[i-2]);
        }
        return f[nums.size()-1];
    }
};

题目链接：杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

方法一：动态规划

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        ans.push_back({1});
        for (int i = 1;i < numRows;i++) {
            vector<int> tmp;
            for (int j = 0;j <= i;j++) {
                
                if (j == 0 || j == i) tmp.push_back(1);
                else {
                    tmp.push_back(ans[i-1][j-1] + ans[i-1][j]);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};