Day38: 动态规划 LeedCode:509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 蓝桥杯: 更小的数

对于动态规划问题，拆解为如下五步曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化(容易数组溢出)
4. 确定遍历顺序
5. 举例推导dp数组

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：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

思路:

1.确定dp数组（dp table）以及下标的含义

dp[i]表示斐波那契数列的第i个数

2.确定递推公式

F(n) = F(n - 1) + F(n - 2)

3.dp数组如何初始化

F(0) = 0，F(1) = 1

4.确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组

0,1,1,2,3,5,8,13,21,34,55........

代码:

class Solution {
    public int fib(int n) {
        if(n<=1) return n;//注意n必须大于1,不然数组越界
       int[] f=new int[n+1];
       f[0]=0;f[1]=1;
       for(int i=2;i<=n;i++){
         f[i]=f[i-1]+f[i-2];
       }
       return f[n];
    }
}

---

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

思路:

1.确定dp数组（dp table）以及下标的含义

ff[i]表示到达第i阶,你有几种走法

2.确定递推公式

F(n) = F(n - 1) + F(n - 2)

3.dp数组如何初始化

我们不需要知道F(0)等于多少,因为本题中n是正整数

F(1) = 1，F(2) = 2

初始化时注意创建的数组位数小于3,会导致溢出情况

4.确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组

0,1,1,2,3,5,8,13,21,34,55........

class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;
        int[] f=new int[n+1];//f[i]表示到达第i阶,你有几种走法
        f[1]=1;
        f[2]=2;
        for(int i=3;i<=n;i++){
            f[i]=f[i-1]+f[i-2];//想要到达第I阶,你只能从第i-1和第i-2的位置来
        }
        return f[n];
    }
}

---

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

思路:

1.确定dp数组（dp table）以及下标的含义

dp[i]表示到达第i阶,你的最小花费

2.确定递推公式

F(n) = min(F(n-1)+cost[i],F(n-2)+cost[i-2]))

3.dp数组如何初始化

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

F(0) = 0，F(1) = 0

初始化时注意创建的数组位数小于2,会导致溢出情况

4.确定遍历顺序

从递归公式F(n) = min(F(n-1)+cost[i],F(n-2)+cost[i-2]))中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5.举例推导dp数组

.........

代码:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //F(n) = min(F(n-1)+cost[i],F(n-2)+cost[i-2])
        if(cost.length<=1){
            return 0;
        }
        int[] dp=new int[cost.length+1];
        //dp[i]:到第i个楼梯的最少花费
        //楼顶是第cos.length个楼梯
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<dp.length;i++){
         dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
}

---

63. 更小的数

时间限制：1.000S  空间限制：256MB

题目描述

小蓝有一个长度均为 n 且仅由数字字符 0 - 9 组成的字符串，下标从 0 到 n - 1，你可以将其视作是一个具有 n 位的十进制数字 num，小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。 

小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 0，这是合法的。

  

输入描述

输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0 ∼ 9），从左至右下标依次为 0 ∼ n − 1。

输出描述

输出一行包含一个整数表示答案。

输入示例

210102

输出示例

8

提示信息

一共有 8 种不同的方案：

1. 所选择的子串的下标为 0 ~ 1，反转后的numnew = 120102 < 210102

2. 所选择的子串的下标为 0 ~ 2，反转后的numnew = 012102 < 210102

3. 所选择的子串的下标为 0 ~ 3，反转后的numnew = 101202 < 210102

4. 所选择的子串的下标为 0 ~ 4，反转后的numnew = 010122 < 210102

5. 所选择的子串的下标为 0 ~ 5，反转后的numnew = 201012 < 210102

6. 所选择的子串的下标为 1 ~ 2，反转后的numnew = 201102 < 210102

7. 所选择的子串的下标为 1 ~ 4，反转后的numnew = 201012 < 210102

8. 所选择的子串的下标为 3 ~ 4，反转后的numnew = 210012 < 210102

数据范围：
1 <= 字符串长度 <= 10

思路:用i,j分别表示子串首尾位置,比较num[i],num[j]的大小,

如果num[j]>num[i],则翻转之后,numnew>num

如果num[j]<num[i],则翻转之后,numnew<num

如果num[j]==num[i],则翻转之后,i++,j--重复num[i]和num[j]的比较 ,直到i>j,说明子串是回文串,翻转后numnew==num;

图解:

动态规划步骤: 

1.确定dp数组（dp table）以及下标的含义

dp[i][j]表示num第i到j位置的子串翻转后是否使得numnew>num

2.确定递推公式

if(num[i]>num[j]) dp[i][j]=1;

if(num[i]<num[j]) dp[i][j]=0;

if(num[i]==num[j])  dp[i][j]=dp[i+1][j-1]

3.dp数组如何初始化

i<j 都是不合法子串:dp[i][j]=0;

i==j都是回文串:dp[i][j]=0;

4.确定遍历顺序

从递归公式dp[i][j]=dp[i+1][j-1]中可以看出，dp[i][j]是依赖 dp[i+1][j-1]，那么遍历的顺序一定是从下到上,从前到后遍历的

5.举例推导dp数组

你们自己举例

代码参考:

 
import java.util.*;
public class Main {
public static  void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	String s=scanner.next();
	boolean[][] dp=new boolean[s.length()][s.length()];
	//初始化
	for(int i=0;i<s.length();i++) {
		for(int j=0;j<=i;j++) {
			dp[i][j]=false;
		}
	}
	int res=0;
	//
	for(int i=s.length()-2;i>=0;i--) {
		for(int j=i+1;j<s.length();j++) {
			if(s.charAt(i)==s.charAt(j))dp[i][j]=dp[i+1][j-1];
			if(s.charAt(i)>s.charAt(j)) dp[i][j]=true;
			if(s.charAt(i)<s.charAt(j)) dp[i][j]=false;
			if(dp[i][j]==true) res++;
		}
	}
	
	System.out.println(res);
}
}

---