432-动态规划算法-三角数组求和

绝地灬酷狼 2022-09-05 06:10 162阅读 0赞

## 题目如下 ##

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

[
    	 [2],
    	[3,4],
       [6,5,7],
      [4,1,8,3]
    ]

**2可以往3或者4走，3可以往6或者5走，4可以往5或者7走，以此类推**

## 解题方法 ##

**自顶向下的最小路径和为?11（即，2?+?3?+?5?+?1?= 11）。**  
**要么从正下方走，要么从右下方走，看哪个值最小**  
**可以自底向上回溯判断，但是会重复求解子问题。**

**但是我们可以只使用 O(n)的额外空间（n 为三角形的总行数）来解决这个问题**

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <vector>
    using namespace std;
    
    int main()
    {
        
    	vector<int> v1 = {
         2 };
    	vector<int> v2 = {
         3,4 };
    	vector<int> v3 = {
         6,5,7 };
    	vector<int> v4 = {
         4,1,8,3 };
    	vector<vector<int>> v = {
         v1,v2,v3,v4 };
    
    	//状态：dp[i][j] : 第i行j列元素开始选择数字，的和的最大值
    	int** dp = nullptr;
    	dp = new int* [v.size()];
    	for (int i = 0; i < v.size(); ++i)//开辟空间
    	{
        
    		dp[i] = new int[v4.size()]();
    	}
    
    	int n = v.size() - 1;
    	for (int i = 0; i < v4.size(); ++i)
    	{
        
    		dp[n][i] = v[n][i];//先把最底层赋值一下
    	}
    
    	for (int i = n - 1; i >= 0; --i)//向上优选
    	{
        
    		for (int j = 0; j < v[i].size(); ++j)//遍历当前行的二维数组
    		{
        
    			dp[i][j] = std::min(dp[i + 1][j], dp[i + 1][j + 1]) + v[i][j];
    		}
    	}
    
    	cout << dp[0][0] << endl;
    
    	//释放dp数组的内存
    	for (int i = 0; i < v.size(); ++i)
    	{
        
    		delete[]dp[i];
    	}
    	delete[]dp;
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/ddaa719cc76646fab060a392f069e83c.png