【Algorithm】三步问题

1.三步问题

1.题目连接

• 三步问题

2.算法原理讲解&&代码实现

• 动态规划–线性dp
  • 线性表示：
    • dp[i]:到达第i级台阶一共有多少种选择。
  • 状态转移方程
    • dp[i]=dp[i-1] dp[i-2] dp[i-3]

代码语言：javascript复制

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

    }
};

2.最小花费爬楼梯

1.题目连接

• 最小花费爬楼梯

2.算法原理讲解&&代码实现

方法1

• 动态规划–线性dp
  • 线性表示：
    • dp[i]:到达第i级台阶需要花费多少钱。
  • 状态转移方程
    • dp[i]=min（dp[i-1] cost[i-1],dp[i-2] cost[i-2]）

代码语言：javascript复制

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

    }
};

方法2

• 动态规划–线性dp
  • 线性表示：
    • dp[i]:从i级台阶出发，爬到顶需要花费多少钱。
  • 状态转移方程
    • dp[i]=min(dp[i 1] cost[i],dp[i 2] cost[i])

代码语言：javascript复制

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        if(n==0||n==1) return 0;
        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] cost[i],dp[i 2] cost[i]);

        }
        return dp[0]>dp[1]?dp[1]:dp[0];
    }
};

3.解码方法

1.题目连接

• 解码方法

2.算法原理讲解&&代码实现

• 动态规划–线性dp
  • 线性表示：
    • dp[i]:到达第i个字符一共有多少种解码方式。
  • 状态转移方程
    • dp[i]=dp[i-1] dp[i-2]

代码语言：javascript复制

class Solution {
public:
    int numDecodings(string s) {
        int n=sizeof(s);
        vector<int> dp(n);
        dp[0]=s[0]=!'0';
        if(n==1) return dp[0];

        if(s[1]!='0'&&s[1]!='0') dp[1] =1;
        int ret=(s[0]-'0')*10 (s[1]-'0');
        if(ret>=10&&ret<=26) dp[1] =1;

        for(int i=2;i<n;i  )
        {
            if(s[i]!='0') dp[i] =dp[i-1];
            int re=(s[i-1]-'0')*10 (s[i]-'0');
            if(re>=10&&re<=26) dp[i] =dp[i-2];
        }
        return dp[n-1];

    }
};

动态规划 算法 原理 algorithm dp

0 人点赞