70.爬樓梯

代碼隨想錄原題，看這篇文章：C++動態(tài)規(guī)劃Part.1|動態(tài)規(guī)劃理論基礎(chǔ)、509.斐波那契數(shù)、70.爬樓梯、746.使用最小花費爬樓梯

118.楊輝三角

題目鏈接：118.楊輝三角

一刷代碼

時間復(fù)雜度和空間復(fù)雜度都造到$O(numRow{s}^2)$了。
基本思路就是先構(gòu)造一個result存儲最終的結(jié)果，然后定義一個dp數(shù)組來計算每一行的結(jié)果。

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> result;for (int i = 0; i < numRows; i++) {vector<int> dp(i + 1, 1); // 行的大小應(yīng)為i+1if (i >= 2) {  // 從第三行開始填充中間的數(shù)for (int j = 1; j < i; j++) {dp[j] = result[i - 1][j - 1] + result[i - 1][j]; // 正確使用result中的前一行}}result.push_back(dp);}return result;}
};

思路

很容易看到一個主要的性質(zhì)：
楊輝三角中每個數(shù)字等于上一行的左右兩個數(shù)字之和。

• 確定dp數(shù)組下標(biāo)和含義
  dp[i][j]等于第i行和第j列的值。

• 確定遞推公式
  遞推公式很容易分析出來：
  dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
  也就是每個數(shù)字等于上一行左右兩個數(shù)字之和，但是需要注意的是， 每一行的最左邊和最右邊的數(shù)字必須是1.

• 初始化dp數(shù)組
  這里應(yīng)該如何初始化呢？
  最直接的方式就是直接全部初始化成1，因為每一行除了第一個和最后一個元素，我們都能通過遞推公式進行推導(dǎo)

• 確定遍歷順序
  在leetcode的題目展示上面已經(jīng)看的很清楚了，
  外循環(huán)從上往下遍歷，內(nèi)循環(huán)從左往右遍歷。
  這里需要注意的是，由于每一行的元素個數(shù)都是變化的，所以關(guān)于行的初始化一定要在外循環(huán)中處理。代碼如下：

for (int i = 0; i < numRows; ++i) {	//先遍歷行dp[i].resize(i + 1); //將第i行的向量大小調(diào)整為i+1dp[i][0] = dp[i][i] = 1;for (int j = 1; j < i; +=j) {	//再遍歷列dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}
}

• 打印dp數(shù)組

還是比較簡單的，這里就不寫了。

CPP代碼

其實思路還是很簡單的，不過代碼實現(xiàn)要一點小技巧，

1. 在這里我們先創(chuàng)建一個大小為numRows的二維向量，其中每一行都是一個空的向量。在這種情況下，ret的初始狀態(tài)是一個包含5行的二維向量，但每行都沒有元素。

vector<vector<int>> dp(numRows);

2. 然后我們在外循環(huán)中給每一行向量再調(diào)整大小，這樣我們在原數(shù)組上做操作，空間復(fù)雜度一下就下來了。

for (int i = 0; i < numRows; ++i) {dp[i].resize(i + 1);...
}

總體代碼如下：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> dp(numRows);for (int i = 0; i < numRows; ++i) {dp[i].resize(i + 1);dp[i][0] = dp[i][i] = 1;for (int j = 1; j < i; ++j) {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];}}return ret;}
};

198.打家劫舍

代碼隨想錄原題，看這篇文章：C++動態(tài)規(guī)劃Part8|198.打家劫舍、213.打家劫舍II、198.打家劫舍III