2022-1-25动态规划day1

题1：

509. 斐波那契数

斐波那契数，通常用 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

 1 class Solution {
 2     public int fib(int n) {
 3         int[] dp=new int[31];
 4         dp[0]=0;
 5         dp[1]=1;
 6         for (int i=2;i<31;i++){
 7             dp[i]=dp[i-1]+dp[i-2];
 8         }
 9         return dp[n];
10     }
11 }

思路：动态规划和递归都可以。

题2：

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

 1 class Solution {
 2     public int coinChange(int[] coins, int amount) {
 3         if (amount==0) return 0;
 4         int[] dp=new int[amount+1];
 5         Arrays.fill(dp,Integer.MAX_VALUE/2);
 6         for (int x:coins){
 7             if (x>amount) continue;
 8             dp[x]=1;
 9         }
10         for (int i=0;i<=amount;i++){
11             for (int x:coins){
12                 if (icontinue;
13                 dp[i]=Math.min(dp[i],dp[i-x]+1);
14             }
15         }
16         return dp[amount]==Integer.MAX_VALUE/2?-1:dp[amount];
17     }
18 }

思路：dp[x]表示x金额花费的最少硬币，首先全部用最大值的一半代替，防止+1时溢出。遍历所有硬币，将硬币的金额全部设置为1，然后遍历数组，用每一个硬币试出最小值。

优化：

1.dp[0]应该等于0，可以省略判断第3行，以及dp[x]=1的步骤。

2.遍历金额再遍历硬币需要排除小于硬币的情况，可以反过来遍历。

 1 class Solution {
 2     public int coinChange(int[] coins, int amount) {
 3         int[] dp=new int[amount+1];
 4         Arrays.fill(dp,Integer.MAX_VALUE/2);
 5         dp[0]=0;
 6         for (int x:coins){
 7             for (int i=x;i<=amount;i++){
 8                 dp[i]=Math.min(dp[i],dp[i-x]+1);
 9             }
10         }
11         return dp[amount]==Integer.MAX_VALUE/2?-1:dp[amount];
12     }
13 }