题目链接：单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

方法一：回溯

class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    bool visited[20][20];
    bool ans = false;
    void dfs(vector<vector<char>>& board, string word,int x,int y,int t) {
        if (t >= word.size()) {
            ans = true;
            return ;
        }
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visited[x][y]) return;
        if (board[x][y] != word[t]) return ;
        visited[x][y] = true;
        for (int i = 0;i < 4;i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            
            dfs(board,word,tx,ty,t+1);
        }
        visited[x][y] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0;i < board.size();i++) {
            for (int j = 0;j < board[0].size();j++) {
                dfs(board,word,i,j,0);
            }
        }
        return ans;
    }
};

题目链接：完全平方数

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

题目链接：零钱兑换

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