动态规划基础

动态规划基础

动���规划类型的题目可以分为四步

• 定义子问题
• 写出子问题的递推关系
• 确定DP数组的计算顺序
• 空间优化（可以优化，可以不优化）

  接下来我们使用力扣的几个例子来看一下动态规划问题：

  70. 爬楼梯

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

  （）

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

  接下来我们按照动态规划的四步骤来

  • 第一步：定义子问题

    我们可以把n阶的阶梯的总数分解为k阶阶梯的数量来计算

  • 第二步：写出子问题的递推关系

    f(x) = f(x-1)+f(x-2)的关系

  • 第三步：确定数组的计算顺序

  • 第四步：空间优化

    class Solution{public:    int climbStairs(int n)    {        if (n public:    int tribonacci(int n)     {        if (n == 0)        {            return 0;        }        if (n == 1 || n == 2)        {            return 1;        }        int dp[n+1];        dp[0] = 0;        dp[1] = 1;        dp[2] = 1;        for (int i = 3; i             dp[i] = dp[i-1] + dp[i-2] + dp[i-3];        }        return dp[n];// 使用滚动数组的方式来优化计算空间        int p = 0, q = 1, r = 1 , m = 2;        for (int i = 3; i