算法笔记（十五）—— 动态规划（暴力递归到动态规划）习题训练！

通过递归到记忆化搜索再到严格表结构的动态规划

递归方法的评价：1. 单可变参数的维度；2. 可变参数的个数

记忆化搜索

在暴力递归中会存在很多的重复计算，可以使用存储结构来实现空间换时间。

严格表结构的动态规划

整理位置之间的依赖关系来达到进一步优化的效果。

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. 连续子数组的最大和 - 力扣（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. 礼物的最大价值 - 力扣（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];}
};