精华内容
下载资源
问答
  • 数塔 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 52855 Accepted Submission(s): 31109 ...在讲述DP算法时候,一个经典例子就是数塔问题,

    数塔

    Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 52855    Accepted Submission(s): 31109


    Problem Description
    在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:

    有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

    已经告诉你了,这是个DP的题目,你能AC吗?
     

    Input
    输入数据首先包括一个整数C,表示测试实例的个数,每个测试实例的第一行是一个整数N(1 <= N <= 100),表示数塔的高度,接下来用N行数字表示数塔,其中第i行有个i个整数,且所有的整数均在区间[0,99]内。
     

    Output
    对于每个测试实例,输出可能得到的最大和,每个实例的输出占一行。
     

    Sample Input
    1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
     

    Sample Output
    30

    简单DP题, 自底向上递推


    #include <iostream>
    #include <string.h>
    using namespace std;
    int num_tower[105][105];
    int dp[110][110];
    int main(){
    	int C;
    	cin >>C;
    	while(C--){
    		int N;
    		cin >>N;
    		for(int  i=0; i<N; i++){
    			for(int j=0; j<=i; j++){
    				cin >> num_tower[i][j];
    			}
    		}
    		memset(dp, 0, sizeof(dp));
    		for(int i=N-1; i>=0; i--){
    			for(int j=0; j<=i; j++){
    				dp[i][j]=max(dp[i+1][j], dp[i+1][j+1])+num_tower[i][j];
    			}
    		}
    		cout << dp[0][0] << endl;
    	}
    	return 0;
    } 








    展开全文
  • 文章目录例题:自顶向下好处自顶向下函数结构详解:划重点:递归结构:递归原理:题目一(强烈建议用递归法):...相比自底向上来说,前期虽然痛苦,但是当你清楚结果体系,熟悉后,你会发现写dp递归法比递推

    例题:

    准备了两道做法几乎相同的二维空间的dp题目

    题目一:LeetCode-64最小路径和
    Leetcode64
    题目二:蓝桥杯-跳跃
    跳跃

    两者区别只在于子问题的个数,题目一的个数只有2个方向,而题目二有9个方向。

    自顶向下的好处

    1. 有助于理解dfs、bfs等等算法。
    2. 相比自底向上来说,前期虽然痛苦,但是当你清楚结果体系,熟悉后,你会发现写dp递归法比递推法写的快得多。
    3. 容错性大,就是用递推方法的话,可能会被一些判断的小错误绊住脚,而递归方法只要base case不出差错,一般没有问题。

    自顶向下的函数结构详解:

    dp函数的结构(可结合代码画递归树理解)无非就是:

    • 递归树的叶子结点的跳出条件->对应base case(决定子问题的深度(个数))、base case一般为最简单的题解子状态
    • 递归函数的主体->对应状态转移方程(递归树的展开)。
    • 非叶子结点(子问题)的跳出条件->将return结果写在递归树展开的后面即可 总的过程:通过状态转移方程不断将递归树延伸,直到触及base case停止延伸,往前执行之前的递归,这样就完成了每个非叶子结点的结果跳出,最终得到题解。

    但要是这样写的话很快就会超时,原因是:递归树上可能大量结点重复计算,这个时候就需要一个备忘录一样的东西将以及计算好的题解保存,可将备忘录添加到base case中来,实际上我说的base case决定递归树的深度不完全正确,准确来说应该是决定子树的深度,因为递归过程实际上是一个入栈和出栈的过程,所以首先计算的是最深的那颗树。

    划重点:

    递归的结构:

    1. base case (决定递归树深度,叶子结点的结果)
    2. 状态转移方程(决定递归树的延伸方式)
    3. 处理完子问题的返回(决定非叶子结点的处理结果)

    递归的原理:

    这方面也没办法讲的明白,递归实际上就是一个后进先出的栈的形式,即递归就是入栈和出栈的过程,根据递归树结合深搜理解是最好的。

    题目一(强烈建议用递归法):

    DP函数递归解决:

    int dp(vector<vector<int>>& grid,vector<vector<int>>&memo,int x,int y){
          if(x<0||y<0) return 666;
          //base case:
          if(x==0&&y==0) return grid[x][y];
          if(memo[x][y]!=-1) return memo[x][y];
          
          //condition transfer:
          int a = min(dp(grid,memo,x-1,y),dp(grid,memo,x,y-1));
          //更新备忘录
            memo[x][y] = a + grid[x][y];
        return memo[x][y];
      }     
    

    DP递推解决:

    int dp(vector<vector<int>>& grid) {
            int dx[] = {-1,0};
            int dy[] = {0,-1};
            int x,y;
            for(int i=0;i<grid.size();i++){
                for( int j=0;j<grid[i].size();j++){
                    int tmp = INT_MAX;
                    for(int k =0;k<2;k++){
                        x = i+dx[k];y=j+dy[k];
                        if(x>=0&&y>=0){
                            tmp = min(tmp,grid[x][y]);
                        }
                    }
                    if(tmp!=INT_MAX) 
                    grid[i][j] += tmp;
                }
            }
            return grid[grid.size()-1].back();
        }
    

    题目二(同样建议用递归法)

    DP递归:

    int dp(vector<vector<int>>&grid,vector<vector<int>>&memo,int x,int y){
    int dx[] = {0,0,0,-1,-1,-1,-2,-2,-3};
    int dy[] = {-1,-2,-3,0,-1,-2,0,-1,0};
    //base case:
    if(x<0||y<0)return INT_MIN;
    if(x==0&&y==0)return grid[0][0];
    if(memo[x][y]!=INT_MIN)return memo[x][y];
    //condition transfer:
    int temp = INT_MIN;
    for(int i=0;i<9;i++){
        int q = dp(grid,memo,x+dx[i],y+dy[i]);
        if(q==INT_MIN)continue;
        temp = max(temp,q);
    }//备忘录memo更新
    memo[x][y] = temp + grid[x][y];
    return memo[x][y];
    }
    

    DP递推:

    int dp(vector<vector<int>>&grid){
    int n =grid.size();
    int m =grid[0].size();
      int x[9] = {0,0,0,-1,-1,-1,-2,-2,-3};
      int y[9] = {-1,-2,-3,0,-1,-2,0,-1,0};
      for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
          int temp = INT_MIN;
          for(int t=0;t<9;++t)
          {
            if(i+x[t]>0 && j+y[t]>0){
              temp = max(temp,grid[i+x[t]][j+y[t]]);
            }
          }
          if(trans!=INT_MIN) grid[i][j]+=temp;
        }
        return grid[n-1][m-1];
        }
    
    展开全文
  • dp[i][j]为(i,j)到底边最小路径和,那么得到递推关系式为dp[i][j]=min(dp[i+1][j],dp[i+1][j+1]); 那么很容易写出代码如下: class Solution { public: int minimumTotal(vector<vector<int>>& ...

    在这里插入图片描述
    dp[i][j]为(i,j)到底边的最小路径和,那么得到递推关系式为dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
    那么很容易写出代码如下:

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n=triangle.size();
            vector<vector<int>>dp(n,vector<int>(n,INT_MAX));
            //初始化
            for(int i=0;i<n;i++)
                dp[n-1][i]=triangle[n-1][i];
            for(int i=n-2;i>=0;i--)
                for(int j=0;j<=i;j++)//列号<=行号(注意,这里j不需要逆序,因为递推关系式里是先通过j和j+1去更新j,不用担心子问题的解被覆盖)
                {
                    dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
                }
            return dp[0][0];
    
    
        }
    };
    

    时间复杂度:O(N2)
    空间复杂度:O(N2)

    接下来继续优化,降维处理(很简单的)。

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n=triangle.size();
            vector<int>dp(n,INT_MAX);
            //初始化
            for(int i=0;i<n;i++)
                dp[i]=triangle[n-1][i];
            for(int i=n-2;i>=0;i--)
                for(int j=0;j<=i;j++)列号<=行号(注意,这里j不需要逆序,因为递推关系式里是先通过j和j+1去更新j,不用担心子问题的解被覆盖)
                {
                    dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
                }
            return dp[0];
    
    
        }
    };
    
    展开全文
  • 文章目录题目思路我的思路:我的代码简洁代码自顶向下的思路自顶向下的代码总结 题目 ...思路 我的思路: 一开始考虑不全面, 没考虑0的情况特殊, 当时的...想用递推的, 自底向上的方法解决, 观察后发现, 用str表示字符...

    题目

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

    思路

    我的思路:

    一开始考虑不全面, 没考虑0的情况特殊, 当时的想法:
    想用递推的, 自底向上的方法解决, 观察后发现, 用str表示字符串, 用i表示当前字符串索引值, dp[i]表示[0,i]区间内的解码数, dp[i+1]的值有两方面构成, 分别是dp[i] 和 dp[i-1] (前提是str[i+1]可以和str[i]构成合法的解码).
    大致思路是对的, 但是0比较特殊, 通过一次错误的提交, 我发现 0 是不可以作为前导的, 也就是说01不等于1, 换句话说0只能和前面的数字结合构成两位数.
    考虑0的情况, 因为只和前面的一位结合, 那么前一位必定不能是大于2并且不能等于0, 因为等于0就构成两位以上的数字了, 不可能解码.
    由于从前往后递推, 那么0的出现, 导致了后面的再取值时需要判断一下. 偷懒用了三元运算符…

    我的代码

    class Solution {
    public:
        int numDecodings(string s) {
            int len = s.size();
            vector<long long> dp(len+1);
            
            dp[0] = len ? 1 : 0;
            
            for( int i = 1; i <= len; ++i ){
                if( s[i-1] == '0' && ( i == 1 || zero( s[i-2] ) ) ) return 0;
                
                dp[i] = ( s[i-1] == '0' ? 0 : dp[i-1] ) + ( i > 1 ? s[i-2] == '0' ? 0 : (fun( s[i-2]-'0', s[i-1]-'0' ) ? dp[i-2] : 0) : 0 );
            }
            return dp[len];
        }
        
        int zero( char a ){
            if( a == '0' || a > '2' ) return 1;
            return 0;
        }
        
        int fun(int a, int b){
            if( a*10+b <= 26 ) return 1;
            return 0;
        }
    };
    

    简洁代码

    int numDecodings(string s) {
            int n = s.size();
            vector<int> dp(n+1);
            dp[n] = 1;
            for(int i=n-1;i>=0;i--) {
                if(s[i]=='0') dp[i]=0;
                else {
                    dp[i] = dp[i+1];
                    if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) dp[i]+=dp[i+2];
                }
            }
            return s.empty()? 0 : dp[0];   
        }
    

    自顶向下的思路

    根据上述思路可以发现0的出现是具有"后效性"的, 所以写起来要考虑的地方多一些. 换个思路想一下: 从后往前, 或者自顶向下的记忆化搜索.
    用dp[i]表示从i开始到str的最后一个字符的解码数, 那么不考虑特殊情况状态转移是dp[i-1] = dp[i] + dp[i+1].
    考虑0的情况, 如果一个str以0开头, 那么肯定是无法解码的, 返回0, 假设当前为i, 则dp[i-1] = dp[i+1].
    而累加dp[i+1]的条件是 str[i-1]和str[i]构成合法解码. 为了不重复计算, 要用一个数组保存计算过的结果.

    自顶向下的代码

    int numDecodings(string s) {
            int n = s.size();
            vector<int> mem(n+1,-1);
            mem[n]=1;
            return s.empty()? 0 : num(0,s,mem);   
        }
        int num(int i, string &s, vector<int> &mem) {
            if(mem[i]>-1) return mem[i];
            if(s[i]=='0') return mem[i] = 0;
            int res = num(i+1,s,mem);
            if(i<s.size()-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) res+=num(i+2,s,mem);
            return mem[i] = res;
        }
    

    总结

    DP还不熟练, 继续练吧.

    展开全文
  • 文章目录递归与递推动态规划与递归贪心算法与动态规划知乎关于动态规划问题的一个问答总结!参考文献 ...这是一种自底向上的方法。 递推最初状态最终状态 动态规划与递归 动态规划通常是用递推(自...
  • 存储和遍历

    2021-04-23 17:05:40
    常用于自底向上的递推问题中。 邻接表 对于无根树:为每个结点开辟一个线性列表,记录所有与之相连的结点。 vector<int> adj[N]; 对于有根树: 方法一:若给定的是无向图,则仍可以上述形式存储。 ...
  • 分析:递推的经典题目,自底向上递推。当状态保存在a[n][j]时可省去dp数组,空间可优化。 代码1: /************************************************ * Author :Running_Time * Created ...
  • 动态规划也是把原始问题分解为若干个子问题,然后自底向上,先求解最小子问题,把结果存在表格中,在求解大子问题时,直接从表格中查询小子问题解,避免重复计算,从而提高算法效率。 递归是一个过程或函数...
  • 文章目录动态规划递归写法(自顶向下)递推写法(自底向上)核心思想 动态规划(Dynamic Programming, DP)是一种用来解决一类最优化问题算法思想。 简单来说,动态规划是将一个复杂问题分解成若干个子问题,通过...
  • 目标:求出矩阵连乘MMi+1┅Mj-1Mj(ij) 所需的最少乘法次数 描述最优解结构 递归地定义最优值(写出...以自底向上的递推方式计算出最优值  根据计算最优值时得到的信息,以递归方法构造一个最优解 ...
  • 最长递增子序列题目题目大意思路朴素的递归算法自顶向下的备忘录法(递归+记忆化)自底向上的递推算法 题目 Description A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of...
  • 递推:(自底向上,从小到大)  由递推关系式:dp(T) = min(dp(T - vi)) + 1, 其中T-vi  由于dp(T)值需要有dp(T-vi)值得到,因此递推方法需要数组记录dp(1)……dp(T)值,这样当dp(T) = 0时,可以...
  • 总括 动态规划基本步骤: 找出 ... 递归是自顶向下的分解 动态规划就是自底向上的递推。把递归的每个状态表示出来 再按照动态规划的顺序推 自然就能看出联系 例题分析 HUD 2084 Problem Description 在讲述DP算
  • 一、递归与尾递归 人有人思维,计算机有计算机思维,它们很不相同。如果你要问其中最大不同是什么,那就是一种被称为递归(recursive)逆向思维。...自底向上递推(或回归)求得原问题解。
  • 题目:有一个由非负整数组成...采用递推自底向上的方式,由倒数第二层开始,计算相邻下一层的两个路径和的最大值并与当前值相加,如下所示: 状态转移方程:a[i][j] += max(a[i+1][j] , a[i+1][j+1]); 代码: ...
  • hdoj水题练习(六)

    2018-04-20 20:44:26
    DP系列,虽然个人觉得第一题没那么典型,不过确实也用到了自底向上的递推。hdoj 2062思路:递推求解每个分组中数的个数注意:1、long long 和 %lld(Runtime Error(ACCESS_VIOLATION) or WA...) 2、字典序 3、m要...
  • 一、D&C:分而治之,它是一种著名递归式问题解决方法。... 自顶向下叫做递归,自底向上叫做递推// 问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级台阶总共有多少种跳...
  • 最大连续子序列和题目分析朴素的递归策略(未用到动态规划)改进:自顶向下的备忘录法自底向上的递推方法 题目 给出一个整数序列S,其中有N个数,定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的...
  • 4-1 算法的复杂性有时间复杂性和空间复杂性之分。 4-2 若存在两个正的常数c和n0,对于任意n≥n0,都有T(n)≤c×f(n)...动态规划是自底向上的递推求解。 4-6 回溯法搜索解空间树时,常用的两种剪枝函数为 约束函数和限界
  • http://acm.pku.edu.cn/JudgeOnline/problem?id=2081一道很简单的动态规划,根据一个递推公式求一个序列,我选择顺序的求解,即自底向上的递推,一个int数组result根据前面的值依此求出序列的每一个结果,另外一个...
  • 楼梯问题

    2009-11-09 08:19:42
    hl给我的几道某公司的算法题: 1、 有个 100 级的楼梯,你可以每次跨 1级或2级,问跨到100级总共有...使用自底向上的递推的动态规划算法来避免重复计算: int fib(int n){ int f0 = 1,f1 = 1; int i; ...
  • 题目: 输入括号 ... 经典dp题,如果用dp自底向上的递推做的话,比较麻烦,其实用记忆化做很简单, 每次递归前加上判断是否已经计算过即可减少计算量,相当于dfs里的剪枝,代码如下 #include ...
  • 输入括号 输入:(注意:据说有空行,用... 经典dp题,如果用dp自底向上的递推做的话,比较麻烦,其实用记忆化做很简单, 每次递归前加上判断是否已经计算过即可减少计算量,相当于dfs里的剪枝,代码如下 #in...
  • 一.递归:函数调用自身 ...自底向上,解决掉了存在重复用问题 例子:斐波那契数列 三.分治:大问题分解为小问题,再整合成大问题。满足: 1) 该问题规模缩小到一定程度就可以容易地解决 2) 该问题
  • 图是一个数塔,要求找出一条路径,使路径上的数组和最大 【Input】 第一行是一个整数N,表示数塔的高度,接下来用N行数字...在用动态规划考虑数塔问题时可以自顶向下的分析,自底向上的计算。 从顶点出发时到底向左
  •   <br /> 在用动态规划考虑数塔问题时可以自顶向下的分析,自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求...
  • 递归算法时自顶向下思想,中间有太多重复计算,而动态规划自底向上递推求解,用表(通常为数组)记录子问题的解,以便保存和以后的检索,从最简单的问题的解填起,以自底向上的方式填表,这就保证了当我们求解一个子...
  • 动态规划入门

    2018-09-18 14:20:00
    动态规划 一、几个要点  1、主体思想:同一件事件不做第二次;  2、状态表示:用问题某些特征参数描述当前... 自底向上递推形式。 二、可以使用动态规划题目特点:  1、一个大问题可以划分为若干子问...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 197
精华内容 78
关键字:

自底向上的递推