动态规划感悟1

下面的感悟主要还是基于力扣上面动态规划（基础版）得出来的相关的做题结论

动态规划（基础版） - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

首先是

斐波那契类型的动态规划
70. 爬楼梯 - 力扣（LeetCode）

主要的方法就是需要知道下面的公式
$$f(x)=f(x-1)+f(x-2)$$
也就是说爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。然后就是确定边界条件：我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。

后面的快速矩阵幂和公式法可以看官方的题解

// 这段代码的时间复杂度是最低的
class Solution
{
public:int climbStairs(int n){vector<int> dp(n + 1, 0);dp[0] = 1;dp[1] = 1;for (int i = 2; i < n + 1; i++)dp[i] = dp[i - 1] + dp[i - 2];return dp[n];}
};
// 时间复杂度比较的高，空间复杂度还是比上面的代码好一点
class Solution
{
public:int climbStairs(int n){int a = 1, b = 1, temp;for (int i = 1; i < n; i++){temp = a;a = b;b = b + temp;}return b;}
};

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

和爬楼梯是一样的解法

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

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

是上面两道题目的变体，需要确定如下的递推关系：
$$T(n)=T(n-1)+T(n-2)+T(n-3)$$

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

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

要想使用动态规划，主要是需要确定好状态转移方程。不妨以dp[i]表示达到下标i的最小花费。

则dp[0]=dp[1]=0,这是边界条件。

当 2≤i≤n 时，可以从下标 i−1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i−2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下：

$$dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])$$
然后在进行计算，可以最终求出来dp[n]的最小花费出来。

当然，注意到当 i≥2 时，dp[i] 只和 dp[i−1] 与 dp[i−2] 有关，因此可以使用滚动数组的思想，将空间复杂度优化到 O(1)。

// 时间复杂度和空间复杂度都是O(n)
class Solution
{
public:int minCostClimbingStairs(vector<int> &cost){int length = cost.size();if (length == 0)return 0;if (length == 1)return cost[0];if (length == 2)return min(cost[0], cost[1]);vector<int> dp(length + 1, 0);for (int i = 2; i < length + 1; i++)dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);return dp[length];}
};// 使用滚动数组
class Solution
{
public:int minCostClimbingStairs(vector<int> &cost){int n = cost.size();int prev = 0, curr = 0; // prev代表指向curr的前一个位置for (int i = 2; i <= n; i++){int next = min(curr + cost[i - 1], prev + cost[i - 2]);prev = curr;curr = next;}return curr;}
};

198. 打家劫舍 - 力扣（LeetCode）

用dp[i]表示前i间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
$$dp[i]=max(dp[i-2]+nums[i],dp[i-1])$$
边界条件为：
$$\{\begin{array}{llcc}dp[0]& =nums[0]& & \text{只有一间房屋，则偷窃该房屋}\\ dp[1]& =\max (nums[0],nums[1])& & \text{只有两间房屋，选择其中金额较高的房屋进行偷窃}\end{array}$$

// 比较的复杂，但是能够通过
class Solution
{
public:int rob(vector<int> &nums){int length = nums.size();if (length == 0)return 0;if (length == 1)return nums[0];if (length == 2)return max(nums[0], nums[1]);if (length == 3)return max(nums[0] + nums[2], nums[1]);nums[2] = nums[2] + nums[0];int maxm = nums[2];for (int i = 3; i < length; i++){nums[i] += max(nums[i - 2], nums[i - 3]);maxm = max(maxm, nums[i]);}return maxm;}
};// 下面的方法是比较的好的
class Solution
{
public:int rob(vector<int> &nums){int length = nums.size(); // 用来记录数组的长度if (length == 0)return 0;if (length == 1)return nums[0];nums[1] = max(nums[0], nums[1]); // nums[1]用来记录的是前2间房子能够获得的最大金额for (int i = 2; i < length; i++)nums[i] = max(nums[i - 2] + nums[i], nums[i - 1]);return nums[length - 1];}
};// 当然，也是可以使用滚动数组进行求解的。
class Solution {
public:int rob(vector<int>& nums) {int len = nums.size();if (len == 0)return 0;if (len == 1)return nums[0];nums[1] = max(nums[0], nums[1]);int first = nums[0], second = nums[1]; // first始终指向second左侧for (int i = 2; i < len; i++) {int temp = max(nums[i] + first, second);first = second;second = temp;}return second;}
};