目录

动态规划理论基础

解题步骤

LeeCode 509.斐波那契数

动态规划解法

思路

代码

递归解法

LeeCode 70.爬楼梯 

思路

代码

优化

LeeCode 746. 使用最小花费爬楼梯

思路

代码

优化

动态规划理论基础

解题步骤

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

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

LeeCode 509.斐波那契数

509. 斐波那契数 - 力扣（LeetCode）

动态规划解法：

思路：

1.确定dp数组及下标含义：dp[i]：第i个数的斐波那契数值

2.确定递推公式：由题目可知，dp[i] = dp[i - 1] + dp[i - 2];

3.dp数组如何初始化：dp[0] = 0,dp[1] = 1;

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

5.举例递推dp数组

代码：

class Solution {
public:
    int fib(int n) {
    	if (n <= 1) return n;
		vector<int> dp(n + 1);
		dp[0] = 0; dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
    }
};

优化：只维护两个数值即可，不需要记录整个序列。 

class Solution {
public:
    int fib(int n) {
    	if (n <= 1) return n;
		int dp[2];
		dp[0] = 0; dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			int sum = dp[0] + dp[1];
			dp[0] = dp[1];
			dp[1] = sum;
		}
		return dp[1];
    }
};

递归解法： 

class Solution {
public:
    int fib(int n) {
    	if (n < 2) return n;
		return fib(n - 1) + fib(n - 2);
    }
};

LeeCode 70.爬楼梯 

70. 爬楼梯 - 力扣（LeetCode）

思路：

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[0]的斐波那契数列）

代码：

class Solution {
public:
    int climbStairs(int n) {
    	if (n <= 1) return n;
    	vector<int> dp(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];
    }
};

优化： 

class Solution {
public:
    int climbStairs(int n) {
    	if (n <= 1) return n;
    	int dp[3];
    	dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) {
        	int sum = dp[1] + dp[2];
        	dp[1] = dp[2];
        	dp[2] = sum;
		}
		return dp[2];
    }
};

LeeCode 746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

思路：

1.确定dp数组及下标的含义：dp[i]表示到达第i级台阶所花费的最小体力；

2.确定递推公式：dp[i] = min( dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2] );

3.dp数组如何初始化:dp[0] = 0, dp[1] = 0;

4.确定遍历顺序:从前向后遍历cost数组

5.举例推导dp数组

代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    	vector<int> dp(cost.size() + 1);
    	dp[0] = 0; dp[1] = 0;
    	for (int i = 2; i <= cost.size(); i++) {
    		dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
		}
		return dp[cost.size()];
    }
};

优化：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    	int dp0 = 0, dp1 = 0;
    	for (int i = 2; i <= cost.size(); i++) {
    		int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
    		dp0 = dp1; dp1 = dpi;
		}
		return dp1;
    }
};