JLUVicent

理论基础&509斐波那契数列&70爬楼梯&746使用最小花费爬楼梯

 
  • 2023年 03月24日
  • 0 阅读

day38

理论基础

动态规划：DP

  • 动态规划五步曲：
    • 确定dp数组以及下标的含义
    • 确定递推公式
    • dp数组如何初始化
    • 确定遍历顺序
    • 举例推导dp数组

确定递归公式只是其中一步

动态规划如何debug

把dp数组打印出来，看看是不是按照自己思路推导的

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

509.斐波那契数列

题目链接：509. 斐波那契数

解题思路：参考　　　　视频

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

dp[i]定义为：第i个数的斐波那契数值是dp[i]

2.确定递推公式

状态转移方程：dp[i] = dp[i-1] + dp[i-1]

3.dp数组初始化

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

4.确定遍历顺序

根据递推公式确定dp[i] = dp[i-1]+dp[i-2],遍历顺序一定是从前到后遍历的

5.举例推导dp数组

打印dp数组，进行debug

代码给出了递归和动态规划的两种方法，

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
	// 动态规划
	int fib(int n) {
		if (n <= 1) return n;
		//vector<int> dp(2);
		int dp[2];
		dp[1] = 1;
		dp[0] = 0;
		int sum;
		for (int i = 2; i <= n; i++) {
			sum = dp[1] + dp[0];
			dp[0] = dp[1];
			dp[1] = sum;
		}
		return sum;
	}
	// 递归
	int fib1(int n) {
		if (n <= 1) return n;
		return fib1(n - 1) + fib1(n - 2);
	}
};

int main() {
	cout << "请输入正整数n:" ;
	int n;
	cin >> n;
	Solution solution;
	int result = solution.fib1(n);
	cout << "F(n)=" << result << endl;

	return 0;
}

70.爬楼梯

题目链接：70. 爬楼梯

解题思路：参考 视频

本题第一次结合上面的题，利用数学归纳法，发现和斐波那契数列一样，因此直接AC了，就是初始化的dp值不同

1.确定dp数组以及下标的含义：dp[i]:爬到第i层楼梯，有dp[i]种方法

2.确定递推公式：$dp[i] = dp[i-1] + dp[i-2]$

3.dp数组初始化：$dp[1] = 1,dp[2] = 2$

4.确定遍历顺序：从前向后遍历

5.距离推导dp数组：打印dp table，如下图 $n = 5$。

70.爬楼梯

// 时间：O(n)
// 空间：O(1)
// 有种数学归纳法的意思
class Solution {
public:
    int climbStairs(int n) {
        if( n <= 2) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        int sum;
        for( int i = 3; i <= n; i++){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

746.使用最小花费爬楼梯

题目链接：746. 使用最小花费爬楼梯

解题思路：参考 视频

1.确定dp数组以及下标的含义：$dp[i]$:到达第i个台阶所花费的最少体力

2.确定递推公式：$dp[i] = min( dp[i-2] + cost[i-2],dp[i-1] + cost[i - 1]);$ 取花费最小的

3.dp数组初始化：初始时候dp[1]和dp[0]都为0

4.确定遍历顺序：从前向后

5.举例推导dp数组

img

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1); // dp数组的大小应该比原数组要大
        dp[0] = 0;
        dp[1] = 0;
        for( int i = 2; i <= cost.size(); i++){
            dp[i] = min( dp[i-2] + cost[i-2],dp[i-1] + cost[i - 1]);
        }
        return dp[cost.size()];
    }
};
搜索