打印杨辉三角，保存在二维数组中，要求各列对齐
编写程序，打印出如下所示的杨辉三角形（计算结果保存在二维数组中），要求各列保持对齐
a. 要求：不需要输入，通过计算得到二维数组中相关元素的值
i. 可以写int a[7][7] = {1}; 或 int a[7][7] = {{1}, {1, 1}}; 但不能直接写int a[7][7] = {{1}, {1, 1}, {1, 2, 1}, ...};
基于Monster 组和GPT的调写：
#include <iostream>
using namespace std;
int main() {
int n = 7; // 三角形的行数
int a[7][7] = {0}; // 初始化为0
a[0][0] = 1; // 第一行只有一个元素为1
// 计算杨辉三角形的值并保存到二维数组中
for (int i = 1; i < n; i++) {
a[i][0] = 1; // 每行第一个元素为1
for (int j = 1; j < i; j++) {
a[i][j] = a[i-1][j-1] + a[i-1][j]; // 根据杨辉三角形的规律计算出值
}
a[i][i] = 1; // 每行最后一个元素为1
}
// 以对齐的方式打印杨辉三角形
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
- 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7407087
- 这篇博客你也可以参考下：详细易懂注解，二维数组杨辉三角的实现，算法入门
- 除此之外, 这篇博客: 【继动态规划后&计划】回溯算法和动态规划的区别与转换中的 三、动态规划 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
事情没有这么简单，先来算一算，消除重叠子问题之后，算法的时间复杂度是多少？其实最坏情况下依然是 O(2^N)。
为什么呢？因为我们只不过恰好发现了重叠子问题，顺手用备忘录技巧给优化了，但是底层思路没有变，依然是暴力穷举的回溯算法，依然在遍历一棵二叉树。这只能叫对回溯算法进行了「剪枝」，提升了算法在某些情况下的效率，但算不上质的飞跃。
其实，这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题。动态规划总是这么玄学，让人摸不着头脑……
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
sum(A) - sum(B) = target sum(A) = target + sum(B) sum(A) + sum(A) = target + sum(B) + sum(A) 2 * sum(A) = target + sum(nums)综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？
类似的子集划分问题我们前文 经典背包问题：子集划分 讲过，现在实现这么一个函数：
/* 计算 nums 中有几个子集的和为 sum */ int subsets(int[] nums, int sum) {}然后，可以这样调用这个函数：
int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int n : nums) sum += n; // 这两种情况，不可能存在合法的子集划分 if (sum < target || (sum + target) % 2 == 1) { return 0; } return subsets(nums, (sum + target) / 2); }好的，变成背包问题的标准形式：
有一个背包，容量为 sum，现在给你 N 个物品，第 i 个物品的重量为 nums[i - 1]（注意 1 <= i <= N），每个物品只有一个，请问你有几种不同的方法能够恰好装满这个背包？
现在，这就是一个正宗的动态规划问题了，下面按照我们一直强调的动态规划套路走流程：
第一步要明确两点，「状态」和「选择」。
对于背包问题，这个都是一样的，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
翻译成我们探讨的子集问题就是，若只在 nums 的前 i 个元素中选择，若目标和为 j，则最多有 x 种方法划分子集。
根据这个定义，显然 dp[0][…] = 0，因为没有物品的话，根本没办法装背包；dp[…][0] = 1，因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。
我们所求的答案就是 dp[N][sum]，即使用所有 N 个物品，有几种方法可以装满容量为 sum 的背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
PS：注意我们说的 i 是从 1 开始算的，而数组 nums 的索引时从 0 开始算的，所以 nums[i-1] 代表的是第 i 个物品的重量，j - nums[i-1] 就是背包装入物品 i 之后还剩下的容量。
由于 dp[i][j] 为装满背包的总方法数，所以应该以上两种选择的结果求和，得到状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];然后，根据状态转移方程写出动态规划算法：
/* 计算 nums 中有几个子集的和为 sum */ int subsets(int[] nums, int sum) { int n = nums.length; int[][] dp = new int[n + 1][sum + 1]; // base case for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= sum; j++) { if (j >= nums[i-1]) { // 两种选择的结果之和 dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]; } else { // 背包的空间不足，只能选择不装物品 i dp[i][j] = dp[i-1][j]; } } } return dp[n][sum]; }然后，发现这个 dp[i][j] 只和前一行 dp[i-1][…] 有关，那么肯定可以优化成一维 dp：
/* 计算 nums 中有几个子集的和为 sum */ int subsets(int[] nums, int sum) { int n = nums.length; int[] dp = new int[sum + 1]; // base case dp[0] = 1; for (int i = 1; i <= n; i++) { // j 要从后往前遍历 for (int j = sum; j >= 0; j--) { // 状态转移方程 if (j >= nums[i-1]) { dp[j] = dp[j] + dp[j-nums[i-1]]; } else { dp[j] = dp[j]; } } } return dp[sum]; }我的解法：C++；先基础动规，再压缩内存动规。
/** * @Description: 方法二: 动态规划——转为为——子集划分的01背包问题。 * @param {int} S * @return {*} * @notes: */ int findTargetSumWays(vector<int> &nums, int S) { int n = nums.size(); if (n == 0) return 0; int sum = 0; for(int num:nums){ sum+=num; } // 不合法的子集划分 排除掉。 if(sum < S || (sum+S) %2 == 1){ return 0; // 不合法 } // 进入0-1 背包问题中 return subSets(nums, (S+sum)/2); } // helper —— 辅助函数 // 真正的 子集划分01背包问题。 // dp[i][j] i从1开始。 前i个物品，载重为j 最多能有几种方法将背包恰好填满。 int subSets(vector<int>& nums, int target){ int n = nums.size(); vector<vector<int>> dp(n+1, vector<int>(target+1, 0)); // base for(int i=0;i<n+1;i++){ dp[i][0] = 1; } // 遍历 for(int i = 1;i<n+1;i++){ for(int j = 0;j<target+1;j++){ // j=0 开始，因为 还有i=0的 重量/数字呢！ if(j >= nums[i-1]){// 放得下 dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]]; }else{ dp[i][j] = dp[i-1][j]; } } } return dp[n][target]; } /** * @Description: 辅助函数 状态压缩。内存压缩。 * @param {int} target * @return {*} * @notes: */ int subSets(vector<int>& nums, int target){ int n = nums.size(); // 压缩到1维 vector<int> dp(target+1, 0); // base dp[0] = 1; // 遍历 for(int i = 1;i<n+1;i++){ for(int j = target; j>=0;j--){ // 从后到前，防止覆盖上个状态。// j=0 开始，因为 还有i=0的 重量/数字呢！ if(j >= nums[i-1]){// 放得下 dp[j] = dp[j]+dp[j-nums[i-1]]; }else{ dp[j] = dp[j]; } } } return dp[target]; }对照二维 dp，只要把 dp 数组的第一个维度全都去掉就行了，唯一的区别就是这里的 j 要从后往前遍历，原因如下：
因为二维压缩到一维的根本原理是，dp[j] 和 dp[j-nums[i-1]] 还没被新结果覆盖的时候，相当于二维 dp 中的 dp[i-1][j] 和 dp[i-1][j-nums[i-1]]。
那么，我们就要做到：在计算新的 dp[j] 的时候，dp[j] 和 dp[j-nums[i-1]] 还是上一轮外层 for 循环的结果。
如果你从前往后遍历一维 dp 数组，dp[j] 显然是没问题的，但是 dp[j-nums[i-1]] 已经不是上一轮外层 for 循环的结果了，这里就会使用错误的状态，当然得不到正确的答案。
现在，这道题算是彻底解决了。
总结一下，回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造，从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出状态压缩，还得反向遍历。
现在搞得我都忘了自己是来干嘛的了。嗯，这也许就是动态规划的魅力吧。
- 您还可以看一下 郑逊敏老师的抖音快手短视频自媒体制作引流运营兼职创业赚钱盈利实战教程课程中的 避免成为炮灰的“三不”原则小节, 巩固相关知识点