烤漆 东莞网站建设,厦门市建设局网站,找个男做那个视频网站好,2021年关键词有哪些通过递归到记忆化搜索再到严格表结构的动态规划
递归方法的评价#xff1a;1. 单可变参数的维度#xff1b;2. 可变参数的个数
记忆化搜索
在暴力递归中会存在很多的重复计算#xff0c;可以使用存储结构来实现空间换时间。 严格表结构的动态规划
整理位置之间的依赖关系…通过递归到记忆化搜索再到严格表结构的动态规划
递归方法的评价1. 单可变参数的维度2. 可变参数的个数
记忆化搜索
在暴力递归中会存在很多的重复计算可以使用存储结构来实现空间换时间。 严格表结构的动态规划
整理位置之间的依赖关系来达到进一步优化的效果。 322. 零钱兑换 - 力扣LeetCodehttps://leetcode.cn/problems/coin-change/
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint count(amount1 ,amount1);count[0] 0;for(auto coin : coins){for(int i coin ; iamount ; i){count[i] min(count[i] , count[i-coin]1);}}return count[amount]amount1?-1:count[amount];}
}; 518. 零钱兑换 II - 力扣LeetCodehttps://leetcode.cn/problems/coin-change-ii/
class Solution {
public:int change(int amount, vectorint coins) {vectorint count(amount1 , 0);count[0] 1;for(auto coin : coins){for(int i coin ; iamount ; i){count[i] count[i-coin];}}return count[amount];}
};
剑指 Offer 42. 连续子数组的最大和 - 力扣LeetCodehttps://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/?envTypestudy-planidlcofplanlcofplan_progressjkqqk9t
class Solution {
public:int maxSubArray(vectorint nums) {int res nums[0] , pre 0;for(auto num : nums){pre max(prenum , num);res max(res , pre);}return res;}
}; 剑指 Offer 47. 礼物的最大价值 - 力扣LeetCodehttps://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/?envTypestudy-planidlcofplanlcofplan_progressjkqqk9t
// class Solution {
// public:
// int process(vectorvectorint grid , int x , int y , vectorvectorint dp){
// if(xgrid.size()||ygrid[0].size())return 0;
// if(dp[x][y]!0)return dp[x][y];
// dp[x][y] grid[x][y] max(process(grid, x1, y, dp), process(grid, x, y1, dp));
// return dp[x][y];
// }// int maxValue(vectorvectorint grid) {
// vectorvectorint dp(grid.size() , vectorint(grid[0].size() , 0));
// return process(grid, 0, 0, dp);
// }
// };class Solution {
public:int maxValue(vectorvectorint grid) {vectorint dp(grid[0].size()1 , 0);for(int i grid.size()-1 ; i0 ; i--){for(int j dp.size()-2 ; j0 ; j--){dp[j] max(dp[j] , dp[j1]) grid[i][j];}}return dp[0];}
};
