珠寶的最高價值

題目

大佬思路
多開一行使得代碼更加的簡潔

移動到右側和下側
dp[ i ][ j ]有兩種情況：
第一種是從上面來的禮物最大價值：dp[ i ][ j ] = dp[ i - 1 ][ j ] + g[ i ][ j ]
第二種是從左面來的禮物最大價值：dp[ i ][ j ] = dp[ i ][ j - 1 ] + g[ i ][ j ]
所以得出狀態表達式，dp[ i ][ j ] = max( dp[ i ][ j - 1 ]，dp[ i - 1 ][ j ] ) + g[ i ][ j ]
2。為了簡潔代碼，多增加一行

class Solution {public int maxValue(int[][] grid) {int m = grid.length;int n = grid[0].length;//dp[i][j]表示從grid[0][0]到grid[i - 1][j - 1]時的最大價值int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[m][n];}
}class Solution { 
public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return  dp[m][n]; }
};

下降路徑最小和

頭文件： #include< algorithm >
返回值： 兩個函數返回的都是迭代器，所以要提取數值的話需要在函數前加上*
語法格式： max_element(first,end,cmp);其中cmp為可選擇參數（自定義排序可用，默認不需要填）
兩個函數默認都是從小到大排列， max_element() 輸出最后一個值， min_element() 輸出第一個值。
這里要特別注意：如果自定義排序是從大到小的， max_element() 和min_element() 的返回結果相反，也就是說max_element()返回的是最小值，min_element()返回的是最大值 。

• 定義函數dp[i][j] ，是關于路徑到達 i,j 點的最小值
• 然后找 關系式，分析最后一點是從哪里得到的， 從左上方來：dp[ i - 1 ][ j - 1 ] + m[ i ][ j ]，從正上方來：dp[ i - 1 ][ j ] + m[ i ][ j ]， 從右上方來：dp[ i - 1 ][ j + 1 ] + m[ i ][ j ]

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n, vector<int>(n));copy(matrix[0].begin(), matrix[0].end(), dp[0].begin());for (int i = 1; i < n; i++) {for (int j = 0; j < n; j++) {int mn = dp[i - 1][j];if (j > 0) {mn = min(mn, dp[i - 1][j - 1]);}if (j < n - 1) {mn = min(mn, dp[i - 1][j + 1]);}dp[i][j] = mn + matrix[i][j];}}return *min_element(dp[n - 1].begin(), dp[n - 1].end());}
//INT_MAX = 2 ^ 31 - 1，INT_MIN = -2 ^ 31.
//防止越界，在左邊，上面和右邊都增加一行
//并且將第一行定義為0
class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));for (auto& e : dp[0]) e = 0; for (int i = 1; i <= m; i++) {  for (int j = 1; j <= n; j++) {  dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1]))+ matrix[i - 1][j - 1];  }}int ans = INT_MAX;  for (const auto& k : dp[m]) ans = min(ans, k);  return ans;  }
};

使用最小花費爬樓梯

題目

使用遞歸操作的幾個步驟
1.明確dp[]函數的含義
2.明確關系式
3.進行初始化操作
4.確定遍歷操作

class Solution {//本題是要求跳到最后一個臺階+1的位置public int minCostClimbingStairs(int[] cost) {  int len = cost.length;  //dp表示停留在第i個臺階上的花費  int[] dp = new int[len + 1];  //可以從第一個或第0個臺階起跳  dp[0] = 0;  dp[1] = 0;  //到達第i個臺階要么是從dp[i-2]跳兩個臺階上來，要么從do[i-1]跳一個臺階上來  for (int i = 2; i <= len; i++) {  dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);}return dp[len];  }

整數拆分

題目

遞歸操作

1.確定dp數組含義
dp[i]：分拆數字i，可以得到的最大乘積為dp[i]
2.明確關系式
3.數組初始化
4.遍歷順序

大佬講解
（無敵解釋）

class Solution       {
public:/*** 1. 確定dp數組下標含義 分拆數字i，可以得到的最大乘積為dp[i];* 2. 遞推公式 dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j);* 3. 初始化 dp[2] = 1;* 4. 遍歷順序 從前向后遍歷就可以;* 5. 推導結果;*/int integerBreak(int n) {/* 定義dp數組 */vector<int> dp(n + 1);/* dp數組初始化 */dp[2] = 1;/* 從前向后遍歷 */for (int i = 3; i <= n ; i++) {/* j遍歷到小于i的值 */for (int j = 1; j < i - 1; j++) {dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};