案例
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
动态规划思路
1.状态定义
定义一个动态规划数组 dp ，其中 dp[i] 表示和为 i 的完全平方数的最少数量。
2.状态初始化
初始化 dp 数组，因为和为 0 的完全平方数的最少数量是 0 ，所以 dp[0] = 0 。对于所有其他值，可以初始化为一个较大的数（如 n+1 ），表示我们还没有找到解决方案。
3.状态转移方程
对于每个 i 从 1 到 n ，我们需要找到所有可能的完全平方数 jj （其中 jj <= i ），然后更新 dp[i] 的值。状态转移方程可以表示为：其中 j 是从 1 到 sqrt(i) 的整数。
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
4.计算顺序：按照从小到大的顺序计算 dp[i] 的值，因为每个 dp[i] 的值依赖于 dp[i-jj] 的值，其中 jj <= i 。
5.最终结果
最后， dp[n] 将包含和为 n 的完全平方数的最少数量。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = n + 1;
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
动态规划法:
动态规划法介绍:
动态规划（Dynamic Programming，简称 DP）是一种用于解决多阶段决策问题的算法思想，它通过将复杂问题分解为更简单的子问题，并存储这些子问题的解以避免重复计算，从而高效地解决问题。动态规划通常用于优化问题，尤其是那些具有重叠子问题和最优子结构特性的问题。
核心概念
• 最优子结构：
• 一个问题的最优解可以由其子问题的最优解组合而成。换句话说，问题的解可以分解为若干个子问题的解。
• 例如，在爬楼梯问题中，到达第(n)阶的方法数可以由到达第(n-1)阶和第(n-2)阶的方法数组合而成。
• 重叠子问题：
• 在递归求解过程中，同一个子问题会被多次计算。动态规划通过存储这些子问题的解（通常使用一个数组或哈希表），避免重复计算，从而提高效率。
• 例如，在递归计算斐波那契数列时，会多次计算相同的值，而动态规划通过存储这些值来避免重复计算。
动态规划的优势
• 高效性：
• 动态规划通过存储子问题的解，避免了重复计算，大大提高了算法的效率。时间复杂度通常为(O(n))。
• 适用性：
• 动态规划适用于具有重叠子问题和最优子结构特性的问题，如背包问题、最长公共子序列、最短路径问题等。
• 可扩展性：
• 动态规划的思想可以扩展到多维问题，通过增加状态维度来解决更复杂的问题。
动态规划的局限性
• 空间复杂度：
• 动态规划通常需要额外的空间来存储子问题的解，空间复杂度可能较高。例如，爬楼梯问题的空间复杂度为(O(n))。
• 状态转移方程的推导：
• 动态规划的关键在于推导状态转移方程，这需要对问题有深入的理解和分析。
• 适用范围：
• 动态规划只适用于具有重叠子问题和最优子结构特性的问题，对于不符合这些特性的问题，动态规划可能不适用。
总结
动态规划是一种强大的算法思想，通过将复杂问题分解为更简单的子问题，并存储这些子问题的解，避免重复计算，从而高效地解决问题。爬楼梯问题是动态规划的经典应用之一，通过定义状态、初始化状态、状态转移和计算顺序，可以高效地求解问题。