leetcode-动态规划 （穷举最值）
动态规划一般有三个步骤：
（首先，如果问题存在“重叠子问题，那么一般情况下就可以使用 动态规划”）
- 找出最优子结构
- 找到转台转移方程
- 剪枝
1. 斐波那契数列
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，
后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
Related Topics 数组
public int fib(int N) {
if (N <= 1) {
return N;
}
int pre = 0;
int cur = 1;
int ct = 1;
while (ct++ < N) {
int temp = cur + pre;
pre = cur;
cur = temp;
}
return cur;
}
2. 钱币问题
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1
示例2:
输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1
说明：
注意:
你可以假设：
0 <= n (总金额) <= 1000000
Related Topics 动态规划
