【算法】动态规划1，最小花费爬楼梯，解码方法

一、动态规划简介

动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ;

动态规划 , 没有具体的步骤 , 只有一个核心思想 ;
动态规划 的 核心思想 是 由大化小 , 大规模问题 使用 小规模问题 计算结果 解决 , 类似于 分治算法 ;

二、动态规划解题步骤

三、例题

例题1

通过分析最近的一步来划分问题：

class Solution {
   
public:
    int minCostClimbingStairs(vector<int>& cost) {
   
        int n = cost.size();
        vector<int> dp(n+1);
        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[i] 与s[i]和s[i-1] 的解码关系有关；
1.如果s[i]单独解码，在1~9就可以解码，但是题目问的是解码方法的总数，在之前的所有解码类型后面加一个相同的字母，解码方法并不会变化，等于dp[i-1] （上一个dp的解码总数） ，解码总类变了而已，失败就为0。
2.如果s[i]与s[i-1]解码，在10~26内解码成功，但是解码方法总数不会变化，等于dp[i-2] （上两个dp的解码总数），失败就为0.
所以dp[i] = dp[i-1] + dp[i+2];

但是，并不能直接带入，需要依次判断后加入，因为一旦单独解码或者一起解码失败的话就直接归0了。

class Solution {
   
public:
    int numDecodings(string s) {
   
            int n = s.size();
            vector<int> dp(n);//创建dp表

            dp[0] = (s[0] != '0');//初始化dp[0],dp[1]
            if(n == 1) return dp[0];//边界情况
            int ret = (s[0]-'0')*10 + (s[1] - '0');
            if(ret >= 10 && ret <= 26) dp[1]++;
            if(s[1] != '0' && s[0] != '0') dp[1]++;

            //填表
            for(int i = 2; i<n; i++)
            {
   
                if(s[i] !='0') dp[i] +=dp[i-1];//需要依次判断加入
                int t = (s[i-1]-'0')*10 + s[i] - '0';
                if(t >= 10 && t <= 26) dp[i] += dp[i-2];
            }
        return dp[n-1];

    }
};