题目链接

关键词

解析

• 状态定义：dp[i][j] 表示前 i 种硬币中选，刚好组成总金额为 j 的最少硬币数量

• 状态方程：dp[i][j] = min(dp[i - 1][j - cnt * coins[i]], dp[i][j])

• 初始化：
• dp[][] = Arrays.fill(Integer.MAX_VALUE)
• dp[i][0] = 0 // 表示从前i中硬币中选，组成金额为0的最少硬币数量为0

代码

未优化前

优化时间之后

• 优化依据：
• 方程一：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - coins[i]] + 1, dp[i - 1][j - 2 * coins[i]] + 2 ... + dp[i - 1][j - k * coins[i]] + k)
• 方程二：dp[i][j - coins[i]] = max(dp[i - 1][j - coins[i]], dp[i - 1][j - 2 * coins[i]] + 1, dp[i - 1][j - 3 * coins[i]] + 2 ... + dp[i - 1][j - k * coins[i]] + k - 1)
• 联立可得：dp[i][j] = max(dp[i - 1][j], dp[i][j - coins[i]])

优化空间之后

相似题目