算法笔记/USACO Guide GOLD金组DP 1. Introduction to DP

USACO Guide中金组的内容分为一下六个章节

• DP
• 数学
• 图论
• 数据结构
• 树
• 一些附加主题

今天学习DP，以下内容：

• 初入DP
• 背包DP
• 图表中的路线
• 最长递增序列
• 状态压缩DP
• 区间DP
• 数位DP

---

初入DP

Dynamic Programming (DP) is an important algorithmic technique in Competitive Programming from the gold division to competitions like the International Olympiad of Informatics. By breaking down the full task into sub-problems, DP avoids the redundant computations of brute force solutions.

动态规划（DP）是信奥中需要掌握的一种重要算法能力，从金组到国际信息学奥林匹克竞赛(IOI)等。通过将整个任务分解为子问题，DP 避免了强力解决方案的冗余计算。

There are two uses for dynamic programming:

DP的两种用法：

• Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
• Counting the number of solutions: We want to calculate the total number of possible solutions.
• 寻找最优解：当题目要求找到尽可能大或尽可能小的解决方案时可以使用DP。
• 计算解决方案的数量：想要计算可能的解决方案的总数时可以使用DP。

We will first see how dynamic programming can be used to find an optimal solution, and then we will use the same idea for counting the solutions. Understanding dynamic programming is a milestone in every competitive programmer’s career. While the basic idea is simple, the challenge is how to apply dynamic programming to different problems. This chapter introduces a set of classic problems that are a good starting point.

我们将首先了解如何使用动态规划来找到最佳解决方案，然后我们将使用相同的想法来计算解决方案。理解动态编程是每个信奥学生中的一个里程碑。虽然基本思想很简单，但挑战在于如何将动态规划应用于不同的问题。本章介绍了一组经典问题，这是一个很好的起点。

---

经典问题

Coin Problem 硬币问题

题目

Given a set of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to form the sum n using as few coins as possible.

今有面值 = {c1, c2,..., ck} 元的硬币各无限枚，想要凑出 n 元，问需要的最少硬币数量。

解法

Let solve(x) denote the minimum number of coins required for a sum x. The values of the function depend on the values of the coins. 

可以使用递推的方式解决这个问题。假设 solve(x) 函数表示总和 x 所需的最小硬币数量，并且该函数的值取决于硬币的面值。

For example, if coins = {1,3,4}, the first values of the function are as follows:

比如，现在我们有的硬币面值有 1, 3, 4 拿来凑钱币那么函数的答案如下：

solve(0) = 0

solve(1) = 1

solve(2) = 2

solve(3) = 1

solve(4) = 1

solve(5) = 2

solve(6) = 2

solve(7) = 2

solve(8) = 2

solve(9) = 3

solve(10) = 3

从而得出递推公式

solve(x) = min(solve(x−1)+1, solve(x−3)+1, solve(x−4)+1). 

Longest increasing subsequence 最长递增子序列