动态规划问题-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