当前位置：首页 > article >正文

【leetcode详解】爬楼梯:DP入门典例(附DP通用思路同类进阶练习)

article 2024/9/16 17:49:18

实战总结：

vector常用方法：

创建一个长为n的vector，并将所有元素初始化为某一定值x

vector<int> vec(len, x)

代码执行过程中将所有元素更新为某一值x

fill(vec.begin(), vec.end(), x)

// 更多实战方法欢迎参考文章：

【vector】常用实战方法：增删改查（C++入门必看）_vector 增删查改-CSDN博客

题面

DP&记忆化通用思路总结

//DP思想: 寻找与原问题同类的更小的子问题
//确定更小的同类问题: 可以用递归
//发掘大小问题的通用逻辑: 递归函数写什么
- //递归函数基本构成:
  - //确定这个递归函数返回什么结果
  - //递归结束条件
  - //递归函数主体
//什么时候用记忆化:
- //存在大量重复计算时 <=> 递归函数参数相同,那么结果必然一样

AC代码见下，思路已在注释中清晰体现：

class Solution {
public:
    int climbStairs(int n) {
    	vector<int>rem(n+1, 0);
		//rem[i]用来记忆还有i级台阶时有多少种走法
		auto dfs = [&](auto& dfs, int i) -> int{
        //dfs返回：当还有i级台阶要走时，一共有几种走法。

			if(i < 0) return 0;//递归返回条件
			else if(i == 0) return 1;
            else if(rem[i] != 0) return rem[i];
			
            int res = 0;
			res += dfs(dfs, i-1);//最后一步走一级台阶
			res += dfs(dfs, i-2);//还是走两步？
                                 //两种走法相互独立，所以采用加法原理
            rem[i] = res;//记忆化
			return res;	
		};
		return dfs(dfs, n);
    }
};