通過遞歸到記憶化搜索再到嚴(yán)格表結(jié)構(gòu)的動(dòng)態(tài)規(guī)劃

遞歸方法的評(píng)價(jià)：1. 單可變參數(shù)的維度；2. 可變參數(shù)的個(gè)數(shù)

記憶化搜索

在暴力遞歸中會(huì)存在很多的重復(fù)計(jì)算，可以使用存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)空間換時(shí)間。

嚴(yán)格表結(jié)構(gòu)的動(dòng)態(tài)規(guī)劃

整理位置之間的依賴關(guān)系來達(dá)到進(jìn)一步優(yōu)化的效果。

322. 零錢兌換 - 力扣（LeetCode）https://leetcode.cn/problems/coin-change/

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> count(amount+1 ,amount+1);count[0] = 0;for(auto coin : coins){for(int i = coin ; i<=amount ; i++){count[i] = min(count[i] , count[i-coin]+1);}}return count[amount]==amount+1?-1:count[amount];}
};

518. 零錢兌換 II - 力扣（LeetCode）https://leetcode.cn/problems/coin-change-ii/

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> count(amount+1 , 0);count[0] = 1;for(auto coin : coins){for(int i = coin ; i<=amount ; i++){count[i] += count[i-coin];}}return count[amount];}
};

劍指 Offer 42. 連續(xù)子數(shù)組的最大和 - 力扣（LeetCode）https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=jkqqk9t

class Solution {
public:int maxSubArray(vector<int>& nums) {int res = nums[0] , pre = 0;for(auto &num : nums){pre = max(pre+num , num);res = max(res , pre);}return res;}
};

劍指 Offer 47. 禮物的最大價(jià)值 - 力扣（LeetCode）https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=jkqqk9t

// class Solution {
// public:
//     int process(vector<vector<int>>& grid , int x , int y , vector<vector<int>>& dp){
//         if(x==grid.size()||y==grid[0].size())return 0;
//         if(dp[x][y]!=0)return dp[x][y];
//         dp[x][y] = grid[x][y] + max(process(grid, x+1, y, dp), process(grid, x, y+1, dp));
//         return dp[x][y];
//     }//     int maxValue(vector<vector<int>>& grid) {
//         vector<vector<int>> dp(grid.size() , vector<int>(grid[0].size() , 0));
//         return process(grid, 0, 0, dp);
//     }
// };class Solution {
public:int maxValue(vector<vector<int>>& grid) {vector<int> dp(grid[0].size()+1 , 0);for(int i = grid.size()-1 ; i>=0 ; i--){for(int j = dp.size()-2 ; j>=0 ; j--){dp[j] = max(dp[j] , dp[j+1]) + grid[i][j];}}return dp[0];}
};