【LeetCode】动态规划刷题训练(一）

02-28 阅读 0评论

文章目录

面试题 08.01. 三步问题
- 题目解析
- 状态转移方程
- 完整代码
- 746. 使用最小花费爬楼梯
- - 题目解析
  - 状态转移方程
  - 完整代码
  - 91. 解码方法
  - - 题目解析
    - 状态转移方程
    - - 情况1：让i位置的数，单独去解码
      - 情况2：让i位置的数和i-1位置的数结合一起去解码
      - 完整代码
        面试题 08.01. 三步问题
        
        点击查看: 三步问题
        $【LeetCode】动态规划刷题训练(一）,【LeetCode】动态规划刷题训练(一）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,方法,费用,第1张$
        （图片来源网络，侵删）
        
        三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
        
        示例1:
        输入：n = 3
        输出：4
        说明: 有四种走法
        示例2:
        $【LeetCode】动态规划刷题训练(一）,【LeetCode】动态规划刷题训练(一）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,方法,费用,第2张$
        （图片来源网络，侵删）
        输入：n = 5
        输出：13
        
        题目解析
        
        当n==1时
        只能从 0走到1 ，即0->1 ，所以只有1 种方法
        
        当n==2时
        可以从 0->2 ，有1种方法
        $【LeetCode】动态规划刷题训练(一）,【LeetCode】动态规划刷题训练(一）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,方法,费用,第4张$
        （图片来源网络，侵删）
        可以从 1->2 ，而0到1 只有1种方法，而1到2只需加一步，所以有2种方法
        最终 1+1 ，共有2种方法
        
        当n==3时
        从0->3 有1种方法
        从1->3 ，因为0->1只有1种方法，而1到3只需加一步，所以有1种方法
        从2->3，因为0->2有2种方法，而2到3只需加一步，所以有2种方法
        最终 1+1+2 ，共有 4种方法
        
        当n==4时
        因为最多一次走 3步，所以 0->4 不成立
        从1->4，因为0->1 有1种方法，而1到4只需加一步，所以有1种方法
        从2->4，因为0->2 有2种方法，而2到4只需加一步，所以有2种方法
        从3->4，因为0->3有3种方法，而3到4只需加一步，所以有3种方法
        最终 1+2+3，共有7种方法
        
        状态转移方程
        
        以i位置为结尾
        dp[i]代表到达i位置时，共有多少种方法
        
        状态转移方程
        以 i 位置的状态，最近的一步划分问题
        
        dp[i]分三种情况考虑，
        从i-1位置到i位置即dp[i-1]
        从i-2位置到i位置即dp[i-2]
        从i-3位置到i位置即dp[i-3]
        
        dp[i]= dp[i-1]+dp[i-2]+dp[i-3]
        
        完整代码
        
        class Solution { public: int waysToStep(int n) { if(n==1||n==2) { return n; } if(n==3) { return 4; } vectordp(n+1); dp[1]=1; dp[2]=2; dp[3]=4; int i=0; for(i=4;i dp[i]=( (dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007; } return dp[n]; } }; public: int minCostClimbingStairs(vector vector dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.size()]; } };
        pfont color="blue"对于状态转移方程，下标为0和下标为1的位置是没办法使用的，会造成越界/pp题中说可以选择从0或者1位置开始爬楼梯代表两个位置是没有花费的/pp即font color="red" dp[0] =0 ,dp[1]=0/font/font/p h291. 解码方法/h2 pfont color="blue"点击查看:解码方法/font/p blockquote pfont color="blue"一条包含字母 A-Z 的消息通过以下映射进行了编码：/pp‘A’ - “1”/pp‘B’ -> “2”
        ‘Z’ -> “26”
        要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
        “AAJF” ，将消息分组为 (1 1 10 6)
        “KJF” ，将消息分组为 (11 10 6)
        注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
        给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。
        题目数据保证答案肯定是一个 32 位的整数。
        
        示例 1：
        输入：s = “12”
        输出：2
        解释：它可以解码为 “AB”（1 2）或者 “L”（12）。
        
        示例 3：
        输入：s = “06”
        输出：0
        解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）。
        
        题目解析
        
        若将其分为1和2，则分别对应 A和B
        若将其看作一个整体，则对应为L
        
        若将其分为0和6，则0没有对应字母
        若将其看作一个整体，不允许存在前导0 表示
        
        状态转移方程
        
        dp[i] 表示以i位置为结尾时，解码方法的总数
        
        情况1：让i位置的数，单独去解码
        
        单独解码的数需要在1-9，所以会存在成功/失败的情况
        
        若解码成功，则i位置对应的数字为1-9之间，相当于把0到i-1位置的所有解码方案后面加上一个字符，
        整体解码的数量就为以i-1位置结尾的数量即dp[i-1]
        
        若解码失败，则全部失败，解码数为0
        如: 60 单独计算，6为F，而0不存在对应数，所以没有解码成功
        
        情况2：让i位置的数和i-1位置的数结合一起去解码
        
        若解码成功，则结合的数字为 10-26之间，相当于在0到i-2位置的所有解码方案后面加上一个字符，
        整体解码的数量就为以i-2结尾的的数量即dp[i-2]
        
        若解码失败，则全部失败，解码数为0
        
        dp[i]=dp[i-1]+dp[i-2]
        dp[i-1] 和dp[i-2]只有在解码成功时，才会加上，否则为0
        
        完整代码
        
        class Solution { public: int numDecodings(string s) { vectordp(s.size()); int i=0; //初始化 if(s[0]!='0') { dp[0]=1; } else { dp[0]=0; } //有可能s字符串只有一个数字 if(s.size()==1) { return dp[0]; } if(s[0]!='0'&&s[1]!='0') { dp[1]++; } //因为s[0]存的是字符，所以选哟减去'0'，从而获取数字 int sum=(s[0]-'0')*10+(s[1]-'0'); if(sum>=10&&sum dp[1]++; } for(i=2;i //说明可以单独编码成功 if(s[i]!='0') { dp[i]+=dp[i-1]; } //说明可以结合编码成功 int sum=(s[i-1]-'0')*10+(s[i]-'0'); if(sum=10&&sum dp[i]+=dp[i-2]; } } return dp[s.size()-1]; } };