746. 使用最小花费爬楼梯
思路: 暴力递归
解题思路
- 把每一种可能都枚举,也就是dfs搜索每一种可能的情况,再求出其中最小的花费返回即可。
代码实现
//求两个数中的最小值
int min (int a, int b) {
return a < b? a: b;
}
//表示从下标i开始到costSize - 1位置的最小花费
int dfs(int i, int* cost, int costSize) {
if (i >= costSize) {//如果已经没有楼梯可以走了,也就是走完了,那么返回0
return 0;
}
int ans = INT_MAX;//表示最终的答案
for (int j = 0; j < 2; j ++) {//枚举两种情况,走一步还是走俩步
if (j) {//走一步的情况,但要其中的最小值
ans = min(ans, cost[i] + dfs(i + 1, cost, costSize));
}
else {//走两步的情况,要其中的最小值
ans = min(ans, cost[i] + dfs(i + 2, cost, costSize));
}
}
return ans;//返回走一步和走两步中的最小花费
}
int minCostClimbingStairs(int* cost, int costSize) {
return min(dfs(0, cost, costSize), dfs(1, cost, costSize));//因为可以从0和1开始,所以取从0和1开始的最小花费
}
这个暴力递归会超时,因此我们可以用记忆化搜索来优化,能用记忆化的原因是因为有重复调用的地方。
解法一:
解题思路
- 因为有重复调用,所以我们加一个缓存表来优化,就可以了,具体思路和上面一样
代码实现
int dp[1001];//缓存表
int min (int a, int b) {
return a < b? a: b;
}
int dfs(int i, int* cost, int costSize) {
//如果已经越界了,也就是爬完了,那么返回0
if (i >= costSize) {
return 0;
}
//如果缓存表里面有,那么直接把缓存表里面的值返回
if (dp[i] != -1) {
return dp[i];
}
int ans1 = cost[i] + dfs(i + 1, cost, costSize);//爬一步的最小花费
int ans2 = cost[i] + dfs(i + 2, cost, costSize);//爬两步的最小花费
dp[i] = min(ans1, ans2);//答案是其中的最小花费
return dp[i];
}
int minCostClimbingStairs(int* cost, int costSize) {
//缓存表初始化为-1
for (int i = 0; i < costSize; i ++) {
dp[i] = -1;
}
//返回从0开始和从1开始爬其中的最小花费
return min(dfs(0, cost, costSize), dfs(1, cost, costSize));
}
解法二:动态规划
解题思路
- 根据前面记忆化搜索的代码我们可以看出来简单的部分是后面的,而复杂的情况是前面的,这个是因为我们的递归定义决定的。
- 所以我们的遍历顺序或者说递推顺序是从右往左推
- 递推公式就是我们的尝试过程,也就是递归函数的调用那里
代码实现
int min (int a, int b) {
return a < b? a: b;
}
int minCostClimbingStairs(int* cost, int costSize) {
int dp[1003] = {0};
for (int i = costSize - 1; i >= 0; i --) {//从右往左推
dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);//通过观察可以优化成这样
}
return min(dp[0], dp[1]);//和记忆化一样也要dp[0] 和 dp[1]中的最小值
}
91.解码方法
思路:暴力递归
//从下标i开始到len的解码方法数
int dfs(int i, char s[], int len) {
if (i == len) {//如果i到了len的位置代表这个方案合法所以返回1,代表这是一个合法的方案,向上传递
return 1;
}
int ans = 0;//最后的方案数
if (s[i] != '0') {//如果s[i]=='0'代表这个方案不合法,返回0
ans += dfs(i + 1, s, len); //一个数字肯定可以解码
if (i + 1 < len && (s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {//如果和下一个数字组合不超过26,那么就可以两个数字一起解码
ans += dfs(i + 2, s, len);
}
}
return ans;
}
int numDecodings(char* s) {
return dfs(0, s, strlen(s));
}
解法一:记忆化搜索
解题思路
- 因为暴力递归重复调用了很多次,所以可以使用记忆化搜索来优化,只需要加一个缓存表
代码实现
int dfs(int i, char s[], int len, int dp[]) {
if (i == len) {
return 1;
}
//如果已经计算过了,那么直接返回已经计算过的答案
if (dp[i] != -1) {
return dp[i];
}
int ans = 0;
if (s[i] != '0') {//如果s[i]=='0'代表这个方案不合法,那么dp[i]的值就是0
ans += dfs(i + 1, s, len, dp);
if (i + 1 < len && (s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {//如果和下一个数字组合不超过26,那么就可以两个数字一起解码
ans += dfs(i + 2, s, len, dp);
}
}
dp[i] = ans;//把已经计算过的位置添加到缓存表里面去
return ans;//返回答案
}
int numDecodings(char* s) {
int dp[101] = {0};//缓存表
int len = strlen(s);
//初始化缓存表为-1
for (int i = 0; i < len; i ++) {
dp[i] = -1;
}
return dfs(0, s, len, dp);
}
解法二:动态规划
解题思路
- 状态转移方程和暴力递归的尝试过程是一样的
- 遍历的顺序是从右往左,因为递归的定义是从i到结尾位置,而简单的状态是递归的终止条件,也就是已知的dp数组的前几项
代码实现
int numDecodings(char* s) {
int dp[101] = {0};//dp[i]代表从i位置到len位置的解码方案数
int len = strlen(s);
dp[len] = 1;//递归的终止条件,就是起始值
for (int i = len - 1; i >= 0; i --) {//从右往左推
if (s[i] != '0') {//只要s[i] != '0',那么方案合法,如果s[i] == '0',那么dp[i]的值就是0
dp[i] += dp[i + 1];//一个数字可以直接解码,所以加上dp[i + 1]
if (i + 1 < len && (s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {//和后面的数字可以被解码
dp[i] += dp[i + 2];//加上dp[i + 2]
}
}
}
return dp[0];
}
639.解码方式||
解题思路
- 和上一道题目的思路是一样的,但是要多一些判断
- 首先对于当前位置有四种情况
- 第一种是当前位置和下一个位置都是数字
- 第二种是当前位置是数字下一个位置是'*'
- 第三种是当前位置是'*'下一个位置是数字
- 第四种是当前位置是'*'下一个位置是'*'
- 分析出这四种情况,这个题目就和上一道题目一样了
解法一:记忆化搜索
代码实现
typedef long long ll;
//返回从下标i到len的方案数
int dfs(int i, char* s, int len, int dp[], ll mod) {
if (i == len) {//如果已经到了结尾位置,代表这个方案合法,所以返回1
return 1;
}
//如果当前位置已经计算过了,那么返回之前计算过的结果
if (dp[i] != -1) {
return dp[i];
}
int ans = 0;//以当前位置的方案数
if (s[i] != '0') {//当前位置不是'0',代表方案合法。如果是'0',返回0
if (s[i] == '*') {//当前位置是'*'
ans += dfs(i + 1, s, len, dp, mod) * 9LL % mod;//先加上选当前位置的方案
if (i + 1 < len) {//如果还有下一个位置
if (s[i + 1] == '*') {//下一个位置是'*'
ans += 15LL * dfs(i + 2, s, len, dp, mod) % mod;//一共有15种可能
}
else {//下一个位置是数字
if (s[i + 1] > '6') {//如果下一个位置的数字大于'6'
ans += dfs(i + 2, s, len, dp, mod) % mod;//那么只有一种可能,'*'只能是1
}
else {//下一个位置的数字小于等于6
ans += 2LL * dfs(i + 2, s, len, dp, mod) % mod;//只有两种可能,'*'可以替换成'1'和'2'
}
}
}
}
else {//当前位置是数字
ans += dfs(i + 1, s, len, dp, mod) % mod;//先加上选当前位置的方案
if (i + 1 < len) {//还有下一个位置
if (s[i + 1] == '*') {//下一个位置是'*'
if (s[i] > '2') {//当前位置的数字大于'2'
ans += 0;//那么'*'替换成什么也不合法
}
else {//当前位置的数字小于等于'2'
if (s[i] == '1') {//当前数字是'1'
ans += 9LL * dfs(i + 2, s, len, dp, mod) % mod;//有9种可能,'*'可以替换成1 ~ 9
}
else {//当前数字是'2'
ans += 6LL * dfs(i + 2, s, len, dp, mod) % mod;//有6种可能,'*'可以替换成1 ~ 6
}
}
}
else {//两个位置都是数字,就和上一题一样的判断
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
ans += dfs(i + 2, s, len, dp, mod) % mod;
}
}
}
}
}
dp[i] = ans % mod;
return ans % mod;
}
int numDecodings(char* s) {
int len = strlen(s);//字符串的长度
ll mod = 1e9 + 7;//需要取模的数字
int dp[100002] = {0};//缓存表
//初始化为-1
for (int i = 0; i < len; i ++) {
dp[i] = -1;
}
return dfs(0, s, len, dp, mod);
}
解法二:动态规划
代码实现
typedef long long ll;
int numDecodings(char* s) {
const int len = strlen(s);
ll mod = 1e9 + 7;
int dp[100003] = {0};
dp[len] = 1;
for (int i = len - 1; i >= 0; i --) {
if (s[i] != '0') {
if (s[i] == '*') {
dp[i] += dp[i + 1] * 9LL % mod;
if (i + 1 < len) {
if (s[i + 1] == '*') {
dp[i] += 15LL * dp[i + 2] % mod;
}
else {
if (s[i + 1] > '6') {
dp[i] += dp[i + 2] % mod;
}
else {
dp[i] += 2LL * dp[i + 2] % mod;
}
}
}
}
else {
dp[i] += dp[i + 1] % mod;
if (i + 1 < len) {
if (s[i + 1] == '*') {
if (s[i] > '2') {
dp[i] += 0;
}
else {
if (s[i] == '1') {
dp[i] += 9LL * dp[i + 2] % mod;
}
else {
dp[i] += 6LL * dp[i + 2] % mod;
}
}
}
else {
if ((s[i] - '0') * 10 + s[i + 1] - '0' <= 26) {
dp[i] += dp[i + 2] % mod;
}
}
}
}
}
dp[i] %= mod;
}
return dp[0];
}
264.丑数
解题思路
- 根据丑数的定义,我们可以知道一个丑数乘以2,3,5还是一个丑数
- 那么根据这个我们就可以得到递推公式了
- 但最优解是三指针的
代码实现
int min(int a, int b) {
return a <= b? a: b;
}
int nthUglyNumber(int n) {
int dp[1691] = {0, 1};
int cnt = 1;//表示现在表里面有几个丑数
//i2是指向乘2的位置,i3指向乘3的位置,i5指向乘5的位置
for (int i = 2, i2 = 1, i3 = 1, i5 = 1; i <= n; i ++) {
int a = dp[i2] * 2;
int b = dp[i3] * 3;
int c = dp[i5] * 5;
int ans = min(min(a, b), c);//三个中最小的那个就是第++cnt个丑数
if (a == ans) {//如果等于第++cnt个丑数,那么去下一个位置
i2++;
}
if (b == ans) {//如果等于第++cnt个丑数,那么去下一个位置
i3++;
}
if (c == ans) {//如果等于第++cnt个丑数,那么去下一个位置
i5++;
}
dp[++cnt] = ans;//放入丑数表
}
return dp[n];
}
标签:题目,int,len,dfs,一维,ans,动态,dp,mod From: https://www.cnblogs.com/lwj1239/p/18016206