C++解OJ题--杨辉三角（动态规划，第一次二维有点紧张）

本文主要是介绍C++解OJ题--杨辉三角（动态规划，第一次二维有点紧张），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言：
  动态规划通俗的说就是利用已知的历史记录来完成未知记录的计算。当我们将一个大问题分解为若干的子问题时，如果子问题之间不是独立的，那么就不适合使用递归，原因是这样会产生重复的计算，并且是爆炸性的，效率不好。
  因而需要使用动态规划来避免重复的计算。

动态规划解题步骤：
 1.定义dp数组所表示的含义
  动态规划我们需要用一个变量来保存历史数据，或者是一维数组，或者是二维数组。我们将这个数组叫为dp(Dynamic Programming)数组。我们要明确数组元素所表示的含义，及数组下标所表示的意思。

 2.确定递推公式
  通俗的讲就是确定数组元素之间的关系。通常通过最后一步和子问题来确定。

 3.定义初始条件及边界
  有些不能由递推公式分解得出的我们要直观的给出答案。边界情况即为数组不能越界

 4.确定遍历顺序（计算顺序）
  按照怎样的遍历顺序进行遍历计算。根据递推公式来进行判断。

原题如下：

  给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
  在「杨辉三角」中，每个数是它左上方和右上方的数的和。

按“步”就搬：
 1.定义dp数组所表示的含义
  本题的问题是让我们生成杨辉三角的前numRows行，但是我们只能一行行的生成，最终结果将会组成杨辉三角。由题意dp数组为一个二维数组更加合适，因而定义第 i 行的数据为dp [ i ][0~i]。

 2.确定递推公式
  最后一步：假设要生成 i 行的杨辉三角，现在已经生成了第 i-1 行的杨辉三角数据。由于第 i-1 行的第0号位置+第1号位置=第 i 行的第1号位置，i-1 行的第1号位置+第2号位置=第 i 行的第2号位置……i-1 行的第i-1号位置+第i号位置=第 i 行的第 i 号位置，所以存在递推公式：dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

 3.定义初始条件及边界
  由于dp[i][0]是不能由递推公式进行分解的所以我们要遍历将dp[i][0]的值全部设置为1；其次这这里不采用将dp数组全部初始化为0，因而dp[i][i]也是不能用递推公式分解得出的，所以将dp[i][i]的值全部设置为1；最后 j 的值是取决于 i 的值即 j <i。

 4.确定遍历顺序（计算顺序）
  由上分析可得该OJ题基本框架为嵌套的两层循环。根据递推公式第一层循环代表行，第二层循环代表列。再者递推公式要求解等式左边的必须知道等式右边的，而（i>i-1;j>j-1)所以第二层循环应该是从小到大的进行计算。

代码实现：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
      vector<vector<int>>dp(numRows);//开辟二维的dp数组
      for(int i=0;i<numRows;i++)//遍历初始化
      {
          dp[i].resize(i+1);//这一步很关键
          dp[i][0]=1;
          dp[i][i]=1;
      }
      for(int i=2;i<numRows;i++)
      {
          for(int j=1;j<i;j++)
          {
              dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
          }
      }
      return dp;
    }
};

  我是老胡，感谢阅读！！❤️ ❤️

这篇关于C++解OJ题--杨辉三角（动态规划，第一次二维有点紧张）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！