Java快速开发学习

锁清秋

leetcode-动态规划 （穷举最值）

动态规划一般有三个步骤：
（首先，如果问题存在“重叠子问题，那么一般情况下就可以使用 动态规划”）

  1. 找出最优子结构
  2. 找到转台转移方程
  3. 剪枝

1. 斐波那契数列

  1. 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，
  2. 后面的每一项数字都是前面两项数字的和。也就是：
  4.  F(0) = 0,   F(1) = 1
  5. F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
  8.  给定 N，计算 F(N)。
  12.  示例 1：
  14.  输入：2
  15. 输出：1
  16. 解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
  19.  示例 2：
  21.  输入：3
  22. 输出：2
  23. 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
  26.  示例 3：
  28.  输入：4
  29. 输出：3
  30. 解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
  35.  提示：
  38.  0 ≤ N ≤ 30
  40.  Related Topics 数组
  1.     public int fib(int N) {
  2.         if (N <= 1) {
  3.             return N;
  4.         }
  5.         int pre = 0;
  6.         int cur = 1;
  7.         int ct = 1;
  8.         while (ct++ < N) {
  9.             int temp = cur + pre;
  10.             pre = cur;
  11.             cur = temp;
  12.         }
  13.         return cur;
  14.     }

2. 钱币问题

  2. 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。
  3.  (结果可能会很大，你需要将结果模上1000000007)
  5.  示例1:
  8.  输入: n = 5
  9.  输出：2
  10.  解释: 有两种方式可以凑成总金额:
  11. 5=5
  12. 5=1+1+1+1+1
  15.  示例2:
  18.  输入: n = 10
  19.  输出：4
  20.  解释: 有四种方式可以凑成总金额:
  21. 10=10
  22. 10=5+5
  23. 10=5+1+1+1+1+1
  24. 10=1+1+1+1+1+1+1+1+1+1
  27.  说明：
  29.  注意:
  31.  你可以假设：
  34.  0 <= n (总金额) <= 1000000
  36.  Related Topics 动态规划