首页 > 其他分享 >一维动态规划题目

一维动态规划题目

时间:2024-02-15 22:34:01浏览次数:28  
标签:题目 int len dfs 一维 ans 动态 dp mod

746. 使用最小花费爬楼梯

力扣题目链接

思路: 暴力递归

解题思路

  1. 把每一种可能都枚举,也就是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开始的最小花费
}

这个暴力递归会超时,因此我们可以用记忆化搜索来优化,能用记忆化的原因是因为有重复调用的地方。

解法一:

解题思路

  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));
}

解法二:动态规划

解题思路

  1. 根据前面记忆化搜索的代码我们可以看出来简单的部分是后面的,而复杂的情况是前面的,这个是因为我们的递归定义决定的。
  2. 所以我们的遍历顺序或者说递推顺序是从右往左推
  3. 递推公式就是我们的尝试过程,也就是递归函数的调用那里

代码实现

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));
}

解法一:记忆化搜索

解题思路

  1. 因为暴力递归重复调用了很多次,所以可以使用记忆化搜索来优化,只需要加一个缓存表

代码实现

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);
}

解法二:动态规划

解题思路

  1. 状态转移方程和暴力递归的尝试过程是一样的
  2. 遍历的顺序是从右往左,因为递归的定义是从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.解码方式||

力扣题目链接

 解题思路

  1. 和上一道题目的思路是一样的,但是要多一些判断
  2. 首先对于当前位置有四种情况
  3. 第一种是当前位置和下一个位置都是数字
  4. 第二种是当前位置是数字下一个位置是'*'
  5. 第三种是当前位置是'*'下一个位置是数字
  6. 第四种是当前位置是'*'下一个位置是'*'
  7. 分析出这四种情况,这个题目就和上一道题目一样了

解法一:记忆化搜索

代码实现

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.丑数

力扣题目链接

解题思路

  1. 根据丑数的定义,我们可以知道一个丑数乘以2,3,5还是一个丑数
  2. 那么根据这个我们就可以得到递推公式了
  3. 但最优解是三指针的

代码实现

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

相关文章

  • 【算法】【动态规划】过桥问题
    1 题目在一个夜黑风高的晚上,有n(n<=50)个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不大于两人通过,他们只有一个手电筒,所以每次过桥的两个人需要把手电筒带回来,i号小朋友过桥的时间为T[i],两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是......
  • 动态规划基础笔记
    背包问题 01背包  一般的动态规划要先考虑好状态,这个状态是一个集合,要能分成几个子集,然后从这些子集(小问题),推到这一整个集合(大问题),且求解过程是一样的,就可以可以转换成大问题分解成小问题一个一个求解,最后合并先要知道状态表示什么再要知道dp的属性,应该跟所求有关,只会......
  • 其他题目合集
    袭击给出\(2n\)个点,求在前\(n\)个和后\(n\)个点中各选一个点的距离的最小值是多少。分治出处:《算法竞赛进阶指南》题解:先考虑只有一种点,怎么求两两距离的最小值。分治,整体的最小距离\(ans=\min(\)左半边的最小值,右半边的最小值,左右之间的最小值\().\)只需考虑左右之......
  • 动态规划题目合集
    3n多米诺问题\(dp[i]\)表示前\(i\)列的方案数,\(dp2[i]\)表示前\(i\)列但是最上面一行缺一个的方案数。\(dp[i],dp2[i]\)可以相互递推,而且刚好是矩阵递推。矩阵快速幂优化。Walk有向无权图。求长度\(k\)的路径条数。我们发现邻接矩阵的\(k\)次方各个元素求和就是......
  • 图论题目合集
    题面:要求把\(1\simn\)排序,满足给定的所有条件,满足条件之后,编号越小要越靠前。(满足条件情况下,先让1最靠左,然后让2……)每个条件会给出两个数\(a,b\),表示\(a\)必须在\(b\)之前。解答:看起来很像拓扑排序。于是我们对于每个条件\(a,b\),从\(a\)向\(b\)连一条边。每......
  • 贪心题目合集
    磁带存储:有\(n\)个磁带,每个片段有两个参数:时长\(t_i\)和频率\(a_i\)。以某种顺序把片段排在磁带里,每个片段的花费为(播放完这个片段的时刻)乘以(该片段的频率)求最小花费和。因为两个片段交换,对之后没有影响。所以可以考虑一个顺序中,如果\(x,x+1\)片段换位置后花费的变化。......
  • vue 父传子 props 静态属性和动态属性
    Props静态属性<template> <div>   <ConpentA title="我是静态props"/> </div></template><script> importConpentAfrom'./components/ConpentA.vue' exportdefault{  components:{   ConpentA......
  • 字符串进阶题目选做
    字符串进阶一些不那么裸的字符串题,甚至出现了parent树优化建图这种离谱的东西。前置知识:kmp,字符串哈希,AC自动机,SA,SAM,ManacherCF914FSubstringsinaString题意:给定字符串,要求支持单点修改,询问时给出字符串,求在\([l,r]\)中出现多少次。思路:考虑一般的字符串维护方法都......
  • SQLSERVER:动态SQL
    --SqlServer动态Sql--动态SQL是指在运行时构造并执行的sql语句。这种技术在sqlserver中非常有用,尤其--是在需要编写灵活且可适应不同情况的代码时。动态sql可以用来创建通用的存储过程,--执行复杂的查询或者在运行时根据特定条件构建SQL语句。--优势与风险:--动态SQL的主要优势......
  • 【题单】一个动态更新的洛谷综合题单
    洛谷试炼场的题目确实很具有代表性,但是近几年以来,又有许多经典题目出现在OI界中,这个大题单就是作为洛谷试炼场的扩展和补充。目录新版本食用指南更新日志题单Part0试机题Part1入门阶段Part2基础算法Part3搜索Part4动态规划Part4.1-4.4动态规划Part4.5-4.12动态规......