专栏首页算法工程师之路动态规划问题-LeetCode 120(动态内存的传递,函数指针,DP)

动态规划问题-LeetCode 120(动态内存的传递,函数指针,DP)

作者:TeddyZhang,公众号:算法工程师之路

动态规划问题:LeetCode #120

1

编程题

【函数声明与函数指针】

在C++中,函数声明形式为:返回值 函数名称(参数类型 参数名称, 参数类型 参数名称) 其中参数名称可以省略不写,记得最后加分号!

定义函数指针和函数声明有些类似,但有一点不同,在函数指针中,函数名为一个指针变量,如下例子中的(*p[2])为一个函数指针数组, 其中p[0] = &max, 相当于对max函数取别名!

#include<iostream>
#include<vector>
using namespace std;

int max(int a, int b) {
    return (a < b) ? b : a;
}

int add(int a, int b) {
    return a + b;
}

int main() {

    int (*p[])(int, int);   // 定义函数指针
    int a, b, c;
    int res1, res2;
    int max(int, int);    // 函数声明

    p[] = &max;
    p[] = &add;
    cin >> a >> b >> c;
    res1 = (*p[])((*p[])(a, b), c);
    cout << res1 << endl;
    res2 = (*p[])((*p[])(a, b), c);
    cout << res2 << endl;

    system("PAUSE");
    return ;
}

【动态内存的传递】

在下面例子中,其中GetMemory1函数中出现了指针作为函数参数进行传递的形式!而指针传递和其他非引用传递一样,都会将实参拷贝出来一份进行传递,因此在函数中形参改变,而实参不改变! 解决这个问题的方法有三种:

  • 使用指针的指针,char **p
  • 在C++中有了引用的符号,因此也可以对指针类型进行引用传递,char* &p
  • 可以利用函数返回值来进行传递(注意返回值是在堆区还是栈区!)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

//char* GetMemory0(int num) {
//    char p[20];
//    return p;
//}     写法错误,返回的是堆栈地址,而堆栈地址在函数结束后会销毁

//void GetMemory1(char* p, int num) {
//    p = (char*)malloc(sizeof(char) * num);
//}    这种写法错误,指针传递属于非引用传递,故函数内指针实为拷贝后完全不同的指针

void GetMemory2(char** p, int num) {
    *p = (char*)malloc(sizeof(char) * num);
}

void GetMemory3(char* &p, int num) {
    p = (char*)malloc(sizeof(char) * num);
}

char* GetMemory4(int num) {
    char* p = (char*)malloc(sizeof(char) * num);
    return p;
}

int main() {

    char* str1 = nullptr;  // 创建指针必须初始化
    GetMemory2(&str1, );
    strcpy(str1, "HELLO");

    cout << str1 << endl;

    free(str1);
    str1 = nullptr;  // 指针free后要置空,防止出现野指针
    system("PAUSE");
    return ;
}

【LeetCode #120】三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形:

[ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

解题思路:

第一种思路:直接暴力递归,将各种情况进行穷举,但是必定会超时,通过递归的方法我们可以得到核心的递归表达式: triangle[x][y] += min(triangle[x+1][y], triangle[x+1][y+1]), 这是由于三角形的下一行只比上一行多一个数的规律导致的! 第二种思路:既然有了递归式,就可以把暴力递归改成动态规划了!这里说一个原地动态规划的解法! 类似于搭积木的原理,从底向上,在每一层都取两个数的最小值加到上一层去,一层层累积上去,直到顶部,最短路径就是triangle[0][0]

暴力递归版

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
       return dfs(, , triangle);
    }
    int dfs(int x, int y,vector<vector<int>>& triangle) {
        if (x == triangle.size() )
            return ;
        return triangle[x][y] + min(dfs(x + , y, triangle),dfs(x + , y + , triangle));
    }
};

动态规划版

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for(int i = triangle.size()-2; i >= ; --i){
            for(int j = ; j < triangle[i].size(); ++j){
                triangle[i][j] += min(triangle[i+][j], triangle[i+][j+]);  
                // triangle[i+1][j+1]不会越界,第i+1行比第i行多一个值
            }
        }
        return triangle[][];
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • gcd,哈希问题-LeetCode 357、355、365、367、380

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。

    算法工程师之路
  • 数字问题-LeetCode 524、525、526、528、530、537、539、540

    LeetCode # 524 525 526 528 530 537 539 540

    算法工程师之路
  • 数字问题-LeetCode 452、453、454、455、456、459(KMP算法)

    在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标...

    算法工程师之路
  • 洛谷P3346 [ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)

    因为所有合法的答案一定是某个叶子节点为根的树上的一条链,因此这样可以统计出所有合法的答案

    attack
  • SPOJ8222 NSUBSTR - Substrings(后缀自动机)

    attack
  • 图论-网络流-最大流--POJ1273Drainage Ditches(Dinic)

    Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

    风骨散人Chiam
  • codeforces 429A(dfs)

    给定一棵树,树的每个结点上有一个值,你可以对树上的值进行异或操作,求使树上的结点值成为目标值所需的最少操作

    dejavu1zz
  • 挑战程序竞赛系列(34):3.2坐标离散化

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 09-排序2 Insert or Merge (25分)

    Insertion sort iterates, consuming one input element each repetition, and growin...

    AI那点小事
  • 1058 合唱队形 2004年NOIP全国联赛提高组

    1058 合唱队形 2004年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结...

    attack

扫码关注云+社区

领取腾讯云代金券