小红的购物车优惠券问题题解一、问题描述1. 题目内容小红的购物车结算金额为 ( n ) 元，她手中有 ( m ) 张优惠券。第 ( j ) 张优惠券的规则为“满 ( a_j ) 元立减 ( b_j ) 元”，即若 ( n >= a_j )，则使用该券后需支付 ( n - b_j ) 元。小红至多使用一张优惠券，请问最少需要支付多少元？2. 输入输出要求输入：第一行输入两个整数 ( n ) 和 ( m )，分别表示结算金额和优惠券数量。接下来 ( m ) 行，每行输入两个整数 ( a_j ) 和 ( b_j )，表示第 ( j ) 张优惠券的满减条件和立减金额。输出：输出使用优惠券后最少需...

一、思路当前操作：计算长度为len的子串A[i...j]是否为回文；子问题：已知更短的子串A[i+1...j-1]是否为回文，推导A[i...j]是否为回文；下一个子问题：若A[i] == A[j]且内部子串是回文，则当前子串是回文；否则不是。二、状态转移方程定义dp[i][j]：子串A[i...j]是否为回文；初始化：dp[i][i] = true（长度为 1 的子串是回文）；状态转移：若A[i] != A[j]：dp[i][j] = false；若A[i] == A[j]：若j - i + 1 == 2（长度为 2）：dp[i][j] = true；否则：dp[i][j] = dp[i+1...

一、思路讲解1. 当前操作遍历到第i种货币时，针对每个金额j，计算使用前i种货币组成金额j的最少货币数，核心是判断是否选择当前货币，并更新最优解。2. 子问题已知使用前i-1种货币组成任意金额的最少货币数（即dp[i-1][...]），推导使用前i种货币组成金额j的最少货币数（即dp[i][j]）；最终通过dp[n][aim]得到使用所有货币组成aim的最少货币数。3. 下一个子问题若不选第i种货币：则dp[i][j]直接继承前i-1种货币组成j的结果（dp[i-1][j]）；若选第i种货币：需满足j >= 当前货币面值coin，且组成j-coin的最少货币数已知（非无穷大），此时dp[...

一、思路讲解1. 当前操作遍历到第i天时，根据当天是否持有股票，分别计算两种状态下的最大现金持有量（dp[i][0]表示第i天无股票时的最大现金，dp[i][1]表示第i天有股票时的最大现金）。2. 子问题已知前i-1天持有/不持有股票的最大现金（dp[i-1][0]和dp[i-1][1]），推导第i天持有/不持有股票的最大现金，最终通过最后一天不持有股票的最大现金（dp[n-1][0]）得到最大收益（因为最后一天持有股票无法获利）。3. 下一个子问题若第i天不持有股票：要么前一天也不持有（保持状态），要么前一天持有且当天卖出（卖出后现金增加当天股价）；若第i天持有股票：要么前一天已持有（保持...

一、思路解析1.简单的想法题目要求是重建一颗二叉树，重建也是建立一颗二叉树。建立一颗二叉树就要从它的结构出发，把每个部分都填上值不就好了吗？ struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; 2.核心思路创建一个节点。给节点的val赋值把它的左子树挂到left上把它的右子树挂到right上把左右子树挂上去之后节点就是一颗树了，把这棵树返回去就是答案。那写代码试一试！！！二、代...