题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。

题解

1. 定义状态：

$dp[i]$表示用所给的面值的硬币凑成金额$i$所需的最少的硬币个数。

2. 设计状态转移方程：

$$ \forall coin \in coins, 当 i \geqslant coin，且 dp[i - coin] \neq -1 时, dp[i] = std::min(dp[i], dp[i - coin] + 1) $$

3. 初始化：

对于 amount...

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题解

这道题是一个非常典型而且很简单的动态规划题目。我们可以根据动态规划题目解题的一般思路来分析：

1. 定义状态：

$dp[i]$表示爬到第$i$级楼梯的不同方法数。由于每次可以选择爬 $1$ 级或者 $2$ 级楼梯， 所以爬到第 $i$ 级楼梯的方法数等于爬到第 $i-1$ 级楼梯和第 $i-2$ 级楼梯的方法数之和。 根据这个关系，我们可以使用动态规划的方式从 $1$ 级楼梯开始逐步计算到第 $n$ 级楼梯的方法数，最终返回 $dp[n]$即为结果。

2. 设计状态转移方程：

$$dp[i] =...

题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

题解

由题可知，数组nums非空，所以分割后的两个子集也必然非空，由于都是正整数，所以nums中元素之和必然为偶数。

这道题是典型的 01 背包问题，假设$dp[i][j]$表示nums中前$i$个元素是否包含和为$j$的子集，那么：

1. 当nums[i] = j的时候，dp[i][j] = true
2. 当nums[i] > j的时候，dp[i][j] = dp[i - 1][j]
3. 当nums[i] < j的时候，dp[i][j] = dp[i - 1][j] || dp[i -...