Java之动态规划之爬楼梯问题

曾经终败给现在 2024-03-27 13:39 81阅读 0赞

**目录**

0.动态规划问题

一.爬楼梯

1.题目描述

2.问题分析

3.代码实现

二.使用最小花费爬楼梯

1.题目描述

2.问题分析

3.代码实现

三. 爬楼梯(进阶版)

1.题目描述

2.问题分析

3.代码实现

四.坏掉楼梯的爬楼梯问题

1.题目描述

2.问题分析

3.代码实现

五.第39级台阶

1.题目描述

2.问题分析

3.代码实现

--------------------

## 0.动态规划问题 ##

**动态规划**(**D**ynamic **P**rogramming)算法的核心思想是:将大问题划分为小问题,进行解决，从而一步步获取最优解的处理算法

动态规划对于解决最优子结构啊和重叠子问题等问题时候,有着很好的应用

对于**动态规划问题**,大致可以分为以下几步:

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

## 一.爬楼梯 ##

### 1.题目描述 ###

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

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

力扣:[力扣][Link 1]

### 2.问题分析 ###

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

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

**dp\[i\]的含义为爬到i层台阶一共有dp\[i\]种方法**

**2.确定递推公式**

**因为每一次可以选择爬`1`或`2`个台阶,所以爬到第i层台阶,可以选择从i-2层(爬2层台阶)到达,也可以选择从i-1层(爬一层台阶)台阶到达,所以爬到第i层的方法数(dp\[i\])等于爬到第i-2层的方法数(dp\[i-2\])加上爬到第i-1层的方法数(dp\[i-1\])**

**所以递推公式为:dp\[i\]=dp\[i-1\]+dp\[i-2\]**

dp[i] = dp[i - 1] + dp[i - 2];

**3.dp数组如何初始化**

**由递推公式可知,推出dp\[i\]需要前两项的值,因此进行初始化的时候,至少对dp\[0\]和dp\[1\]进行初始化赋值,但这个时候dp\[0\]应该是爬到第0层的方法数,这个时候生活常识,不可能有第0层,这个时候我们应该选择dp\[1\]和dp\[2\]进行初始化,爬到第一层就一种,爬一层台阶,爬到第二层可以有两种,第一种直接爬到第二层,也可以借助第一层爬到第二层**

dp[1] = 1;
            dp[2] = 2;

**4.确定遍历顺序**

**由递推公式可知,推出dp\[i\]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序**

**5.举例推导dp数组**

**当n=5时候进行填表**

### 3.代码实现 ###

public int climbStairs(int n) {
            if (n == 1)
                return 1;
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; ++i) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }

## 二.使用最小花费爬楼梯 ##

### 1.题目描述 ###

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

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

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

力扣:[力扣][Link 2]

### 2.问题分析 ###

对于解决这样的动态规划的背包问题,还是采用通用的五个步骤

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

**dp\[i\]的含义:爬到第i个台阶的最低花费**

**2.确定递推公式**

**由题意可知,每一次可以爬一个或者两个台阶,所以可以选择从i-2层,支付第i-2层的花费直接爬到第i层,也可以选择从i-1层,支付第****i-1层的花费直接爬到第i层,只需要从中选择最低的那一个就可以了,所以递推公式为:dp\[i\]=min(dp\[i-2\]+cost\[i-2\],dp\[i-1\]+cost\[i-1\])**

dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

**3.dp数组如何初始化**

**从递推公式可以看出,需要前两项的支撑才可以推出后面一项,所以至少需要对dp\[0\]和dp\[1\],这里可以很清楚的直到爬到第0层就不需要花费,直接跳到第0层台阶,因此dp\[0\]=0,同样的爬到第1层也不需要花费,因为此时可以直接跳两步到达第二层dp\[1\]=0**

dp[0] = 0;
            dp[1] = 0;

**4.确定遍历顺序**

**由递推公式可知,推出dp\[i\]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序**

**5.举例推导dp数组**

对于cost=\{1,100,1,1,1,100,1,1,100,1\}进行填表

### 3.代码实现 ###

public int minCostClimbingStairs(int[] cost) {
            int[] dp = new int[cost.length + 1];
            dp[0] = 0;
            dp[1] = 0;
    
            for (int i = 2; i < cost.length + 1; ++i) {
                dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
    
            }
            return dp[cost.length];
            
        }

## 三. 爬楼梯(进阶版) ##

### 1.题目描述 ###

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

每次你可以weight数组中的步数(如:weight=\{1,2,3\},意思为每次可以爬1个或者2个,或者3个台阶)。你有多少种不同的方法可以爬到楼顶呢？

力扣:[力扣][Link 1]

### 2.问题分析 ###

对于这个问题,前面我们用了最直接的动态规划问题来解决,当我们学习了背包问题之后,我们可以用这个思想来解决这个问题,因为我们每次可以爬1个或者2个,每一次都可以在1个和2个来进行选择,爬几层的这个问题就相当于背包中的物品,n级台阶相当于背包的重量,这样就转换为了**多重背包**的问题,**同时,当可以爬更多次(如:一次可以爬1层或2层或3层........)台阶的时候,多重背包来解决这个问题是更好的.(背包问题指路:**[Java之动态规划的背包问题\_允歆辰丶的博客-CSDN博客][Java_-CSDN]**)**

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

**dp\[i\]的含义是:爬到第i层台阶,有dp\[i\]中方法**

**2.确定递推公式**

**当我们需要到达第i层台阶的时候,此时我们可以选择的是爬1个还是2个(或更多)台阶到达第i层台阶,当我们一步到达的时候dp\[i\]+=dp\[i-1\],当我们两步到达的时候dp\[i\]+=dp\[i-2\].......**

**因此当步数的数组为weight的时候,递推公式**

**dp\[i\]+=dp\[i-weight\[j\]\]**

dp[j] += dp[j - weight[i]];

**3.dp数组如何初始化**

我们需要初始化的就是爬到第0层台阶的方法,此时需要一种方法,将dp\[0\]初始化为1

dp[0] = 1;

**4.确定遍历顺序**

**多重背包问题,遍历方式从左到右**

**5.举例推导dp数组**

### 3.代码实现 ###

int[] weight = {1, 2};
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 0; j <= n; ++j) {//遍历楼梯
                for (int i = 0; i < weight.length; ++i) {//遍历上台阶的步数
                    if (j >= weight[i])//当楼梯的数量大于等于上台阶的步数
                        dp[j] += dp[j - weight[i]];
                }
    
            }
            return dp[n];

## 四.坏掉楼梯的爬楼梯问题 ##

### 1.题目描述 ###

假设你要爬楼梯。楼梯一共有 n 层台阶。因为腿长的限制，每次最多能上 4 层台阶。但是第 5,7 层楼梯坏掉了不能踩。求上楼梯的方案数。

### 2.问题分析 ###

这一题与上一题唯一不同的点就是出现了有些楼梯不能踩的限制,其实这里可以直接使dp\[5\]和dp\[7\]的方法数为0,这样相当于每次都不经过第5和第7层而到达别的楼层

**举例推导dp数组**

> j=0
> 
> \[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\]
> 
> j=1  
> \[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0\]
> 
> j=2  
> \[1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0\]
> 
> j=3  
> \[1, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0\]
> 
> j=4  
> \[1, 1, 2, 4, 8, 0, 0, 0, 0, 0, 0\]
> 
> j=6  
> \[1, 1, 2, 4, 8, 0, 14, 0, 0, 0, 0\]
> 
> j=8  
> \[1, 1, 2, 4, 8, 0, 14, 0, 22, 0, 0\]
> 
> j=9  
> \[1, 1, 2, 4, 8, 0, 14, 0, 22, 36, 0\]
> 
> j=10  
> \[1, 1, 2, 4, 8, 0, 14, 0, 22, 36, 72\]

### 3.代码实现 ###

public static int climbStairs(int n) {
            int[] weight = {1, 2, 3, 4};
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 0; j <= n; ++j) {//遍历楼梯
                if (j == 5 || j == 7)
                    continue;
                for (int i = 0; i < weight.length; ++i) {//遍历上台阶的步数
                    if (j >= weight[i])//当楼梯的数量大于等于上台阶的步数
                        dp[j] += dp[j - weight[i]];
                }
            }
            return dp[n];
        }

## 五.第39级台阶 ##

### 1.题目描述 ###

假设你要爬楼梯。楼梯一共有 n 层台阶。如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的方法呢？

### 2.问题分析 ###

这题与之前题目不同的就是偶数步和奇数步的判断,之前的dp数组是无法判定奇数步还是偶数步的,因此这里需要对dp数组进行一定的改变

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

我们可以增加一个维度,用来存储偶数步和奇数步的方法数,选择二维dp数组dp\[\]\[\]的含义是:爬到第i层台阶,走偶数步的有dp\[i\]\[0\]中方法,走奇数步有dp\[i\]\[1\]种方法

**2.确定递推公式**

**先来分析偶数步到达第i层的递推公式,此时一样可以由奇数步的走一个和两个台阶到达第i层,**

**此时dp\[i\]\[0\]=dp\[i-1\]\[1\]+dp\[i-2\]\[1\]**

**再来来分析奇数步到达第i层的递推公式,此时一样可以由偶数步的走一个和两个台阶到达第i层,**

**此时dp\[i\]\[1\]=dp\[i-1\]\[0\]+dp\[i-2\]\[0\]**

**3.dp数组如何初始化**

**由递推公式可知,至少初始化dp\[1\]\[0\],dp\[1\]\[1\],dp\[2\]\[0\],dp\[2\]\[1\]**

**dp\[1\]\[0\]:偶数步不可能到达第一层dp\[1\]\[0\]=0,爬一级台阶到达第一层,奇数步dp\[1\]\[1\]=1**

**dp\[2\]\[0\]:先爬一层到达第一层,在爬一层到达第二层,一种方法,dp\[2\]\[0\]=1**

**dp\[2\]\[1\]:直接爬两个台阶到达第二层,dp\[2\]\[1\]=1;**

dp[1][0]=0;
            dp[1][1]=1;
            dp[2][0]=1;
            dp[2][1]=1;

**4.确定遍历顺序**

**由递推公式可知,推出dp\[i\]需要前两项的递推出来,所以应该按照从从下到上(从低台阶到高台阶)的遍历顺序**

**5.举例推导dp数组**

**过多,不进行推导了**

### 3.代码实现 ###

public static int climbStairsEven(int n) {
            int[][] dp = new int[n + 1][2];
            dp[1][0] = 0;
            dp[1][1] = 1;
            dp[2][0] = 1;
            dp[2][1] = 1;
            for (int i = 3; i <= 39; ++i) {
                dp[i][0] = dp[i - 1][1] + dp[i - 2][1];
                dp[i][1] = dp[i - 1][0] + dp[i - 2][0];
            }
            return dp[n][0];
    
        }

[Link 1]: https://leetcode.cn/problems/climbing-stairs/
[Link 2]: https://leetcode.cn/problems/min-cost-climbing-stairs/
[Java_-CSDN]: https://blog.csdn.net/qq_64580912/article/details/128618341?spm=1001.2014.3001.5501