【OJ】动归练习一

zxctscl

发布于 2024-03-22 09:02:59

2800

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

1. 前言

做动态规划的题目，有个固定的模式，1.状态表示；2.状态转移方程；3.初始化；4.填表顺序；5.确定返回值。

2. 1137第 N 个泰波那契数

2.1 分析

先根据题目要求先创建dp表vector<int> dp(n+1) 再根据题目已给的定义初始化 dp[0]=0;dp[1]=dp[2]=1; 在循环里面根据题目已给的公式写出循环 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; 最后返回得到的结果return dp[n]; 这里考虑到可能会越界，就得先加一个判断：

if(n==0) return 0;
if(n==1||n==2) return 1;

这个代码空间复杂度为O(n)，优化一下代码，将空间复杂度降到O(1)。

写出几项就会发现，将设置的几个变量连续赋值，就能达到滚动的效果。将b的值先赋给a,在c的值先赋给b,d的值先赋给c。就这样一直到n，最后返回d的值就行。

2.2 代码

class Solution {
public:
    int tribonacci(int n) {
        
        if(n==0) return 0;
        if(n==1||n==2) return 1;
       vector<int> dp(n+1);

        dp[0]=0;
        dp[1]=dp[2]=1;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
};

优化空间后的代码:

class Solution {
public:
    int tribonacci(int n) {
        
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int a=0,b=1,c=1, d=0;
        for(int i=3;i<=n;i++)
        {
            d=a+b+c;
            a=b;
            b=c;
            c=d;
        }
        return d;      

    }
};

3. 面试题 08.01. 三步问题

3.1 分析

假设要到第4个台阶，就可以从第3个台阶到第4个台阶，也可以从第2个台阶到第4个台阶，还可以从第1个台阶到到第4个台阶，总的到第第4个台阶的方法也就是上面加的和。

而到第一个台阶就有1种。到第2个台阶，可以先到1，也可以直接到2，就有两种方法。到第3个台阶，可以直接到，也可以从1到，还可以从2到。而到2的方法有两种。所以到3的方法就有4种。

那么很显然，要到第i个台阶，知道到第i-1和i-2和i-3有多少种就可以了：

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

要先考虑越界的问题，就先判断一下：

    if(n==1||n==2)return n;
    if(n==3)return 4;

题目还要求取模，就直接定义一个int const Mod=1e9+7;用来取模。最后返回return dp[n];就行。

3.2 代码

class Solution {
public:
    int waysToStep(int n) {
    int const Mod=1e9+7;
    if(n==1||n==2)return n;
    if(n==3)return 4;

     vector<int> dp(n+1);
     dp[1]=1;dp[2]=2;dp[3]=4;
     for(int i=4;i<=n;i++)
     {
        dp[i]=((dp[i-1]+dp[i-2])%Mod+dp[i-3])%Mod;
     }
     return dp[n];
    }
};

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

4.1 分析

这里得先明白到达楼梯顶部不是这里顺序表的长度，而是长度再加1。

4.1.1 以i位置为终点

以i位置为终点：要知道到达第i个台阶就得先到达第i-1或者第i-2个台阶，这里选择的是对应花费最小的那一个再加上它对应dp表所对应的值：

dp[i]+=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

在初始化的时候，题目已经给出可以下标为 0 或下标为 1 的台阶开始爬楼梯，那么他们对应的花费就为0：

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

最后返回最小花费：

 return dp[cost.size()];

4.1.2 以i位置为起点

dp[i]表示：从i位置出发，到达楼顶，此时的最小花费。以第i个台阶为起点，就得先到达第i+1或者第i+2个台阶，看一下到达哪个台阶对应的花费低，就到达哪一个台阶。

dp[i]=min(dp[i+1],dp[i+2])+cost[i];

此时初始化的位置就是n-1和n-2：

     dp[n-1]=cost[n-1];
     dp[n-2]=cost[n-2];

最后返回的结果是0和1位置的最小值：

return min(dp[0],dp[1]);

4.2 代码

4.2.1以i位置为终点

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
    
     vector<int> dp(cost.size()+1);
     dp[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()];
    }
};

4.2.2以i位置为起点

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

有问题请指出，大家一起进步！！!

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-21，如有侵权请联系 cloudcommunity@tencent.com 删除

变量