leetcode刷题日记 1

https://leetcode.cn/problems/decode-ways/description/

题目分析

在这里插入图片描述

分析了一下题目，我的第一想法：和之前的上楼梯问题很像

为什么这么说呢，感觉他们的值和他们之前元素都有千丝万缕的联系

就像上楼梯问题

就是我们的dp问题

怎么解释呢？可以理解为将一个大问题分为一个一个的小问题（贪心贪一半（bushi））

我觉得dp问题的最核心的就是**：dp[i]表示什么**

像这个问题就可以将dp[i]表示成i位置是能够解码的方式有多少

其实，仔细的来看，我们每一个i位置都会面临两个情况：

是否1<= s[i]<=9
*是否10<= s[i-1]10+s[i] <=26

这就是判断能不能将其当做一种解法的关键

否则这个i地方的数字将会dp[i]等于0

连锁反应的是是这样的话之后dp表的值都是

原理：

简单来说，我们也说了，每一个s[i]都有两个情况，四种可能

如果1<= s[i]<=9的话那么这种可能的可以行得通，返回dp[i-1],证明这种方法可行

不行的话就会返回0

如果10<= s[i-1]*10+s[i] <=26，那么这种可能的可以行得通返回dp[i-2],证明这种方法可行

不行的话就会返回0

dp[i]就是将这两个可能返回的值加在一起

还要注意初始化，因为我们要用到dp[i-2]，所以我们的得保证dp[i-2]不会溢出，所以当i<2时我们要单独拿出来初始化

代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;class Solution {
public:int numDecodings(string s) {vector<int> bp(s.size() + 1);int ans1 = 0;int ans2 = 0;if (s.size() == 1 && (s[0]-'0') >= 1 && (s[0] - '0') <= 9){ans1 = 1;}else ans1 = 0;bp[0] = ans1;if (s.size() == 2){if ((s[0] - '0') >= 1 && (s[0] - '0') <= 9){ans1 = 1;}else{ans1 = 0;}bp[0] = ans1 ;if ((s[1] - '0') >= 1 && (s[1] - '0') <= 9){ans1 = bp[0];}else{ans1 = 0;}if (((s[0] - '0') * 10) + (s[1] - '0') >=10  && ((s[0] - '0') * 10) + (s[1] - '0') <= 26){ans2 = bp[0];}else{ans2 = 0;}bp[1] = ans1 + ans2;}for (int i = 2; i < s.size(); i++){if ( (s[0] - '0') >= 1 && (s[0] - '0') <= 9){ans1 = 1;}else ans1 = 0;bp[0] = ans1;if ((s[1] - '0') >= 1 && (s[1] - '0') <= 9){ans1 = bp[0];}else{ans1 = 0;}if (((s[0] - '0') * 10) + (s[1] - '0') >= 10 && ((s[0] - '0') * 10) + (s[1] - '0') <= 26){ans2 =1;}else{ans2 = 0;}bp[1] = ans1 + ans2;ans1 = 0;ans2 = 0;if ((s[i] - '0') >= 1 && (s[i] - '0') <= 9){ans1 = bp[i - 1];}else{ans1 = 0;}if (((s[i-1] - '0') * 10) + (s[i] - '0') >= 10 && ((s[i-1] - '0') * 10) + (s[i] - '0') <= 26){ans2 = bp[i - 2];}else{ans2 = 0;}bp[i] = ans1 + ans2;}return bp[s.size() - 1];}
};