做网站被骗,dede网站更新如何同步腾讯微博更新,wordpress 前台上传文件,建盏公司最新消息文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍
198. 打家劫舍 - 力扣#xff08;LeetCode#xff09;
1.1一维数… 文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍
198. 打家劫舍 - 力扣LeetCode
1.1一维数组
class Solution
{
public:int rob(vectorint nums){int n nums.size();if (n 0)return 0;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额vectorint dp(n, 0);dp[0] nums[0];if (n 1)return dp[0];dp[1] max(nums[0], nums[1]);if (n 2)return dp[1];for (int k 2; k n - 1; k){dp[k] max(dp[k - 1], nums[k] dp[k - 2]);}return dp[n - 1];}
};1.2三变量法
class Solution
{
public:int rob(vectorint nums){int n nums.size();if (n 0)return 0;int prv nums[0]; // dp[0]if (n 1)return prv;int cur max(nums[0], nums[1]); // dp[1]if (n 2)return cur;// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额for (int i 2; i n; i){// dp[k] max(dp[k - 1], nums[k] dp[k - 2]);int tmp max(cur, nums[i] prv);prv cur;cur tmp;}return cur;}
};1.3双数组法
class Solution
{
public:int massage(vectorint nums){int n nums.size();if (n 0)return 0;// f[i] 走到i时 偷nums[i]// g[i] 走到i时 不偷nums[i]vectorint f(n);vectorint g(n); // auto g f;f[0] nums[0];for (int i 1; i n; i){f[i] nums[i] g[i - 1];g[i] max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};
2.打家劫舍2
打家劫舍2
2.1双数组法
class Solution {
public:int rob(vectorint nums) {int n nums.size();return max(nums[0] rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vectorint nums, int left, int right) {if (left right)return 0;int n nums.size();vectorint f(n);auto g f;f[left] nums[left];for (int i left 1; i right; i) {f[i] g[i - 1] nums[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[right], g[right]);}
};2.2 三变量法
class Solution
{
public:int robRange(vectorint nums, int start, int end){int n end - start 1;if (n 0)return 0;int prv nums[start]; // dp[k-2]if (n 1)return prv;int cur max(nums[start], nums[start 1]); // dp[k-1]if (n 2)return cur;for (int i start 2; i end; i){// dp[k] max(dp[k - 1], nums[k - 1] dp[k - 2]);int tmp max(cur, nums[i] prv);prv cur;cur tmp;}return cur;}int rob(vectorint nums){int n nums.size();if (n 1)return nums[0];else if (n 2)return max(nums[0], nums[1]);else if (n 3)return max(max(nums[0], nums[1]), nums[2]);// 偷nums[0]不能偷nums[1]和nums[n-1] 能偷[2, n - 2]// 不偷nums[0] 能偷[1, n - 1]return max(nums[0] robRange(nums, 2, n - 2), robRange(nums, 1, n - 1));}
};
3.打家劫舍3
3.1动态规划
class Solution
{
public:unordered_mapTreeNode *, int is, no;void dfs(TreeNode *node){if (node nullptr)return;dfs(node-left);dfs(node-right);is[node] node-val no[node-left] no[node-right];no[node] max(is[node-left], no[node-left]) max(is[node-right], no[node-right]);}int rob(TreeNode *root){dfs(root);return max(is[root], no[root]);}
};3.2双变量法
struct SubtreeStatus
{int is;int no;
};class Solution
{
public:SubtreeStatus dfs(TreeNode *node){if (node nullptr)return {0, 0};auto left dfs(node-left);auto right dfs(node-right);int selected node-val left.no right.no;int notSelected max(left.is, left.no) max(right.is, right.no);return {selected, notSelected};}int rob(TreeNode *root){auto rootStatus dfs(root);return max(rootStatus.is, rootStatus.no);}
};
4.删除相邻数字的最大分数
删除相邻数字的最大分数_牛客题霸_牛客网 (nowcoder.com) 一个数组选了x可以得x分 但是值为x-1和x1的数将会消失 直到数字全被消失或选择 问最高分数遍历数组arr 填充hash arr中的per在hash中作下标 表示 【谁 出现的总和】如4在arr中出现了2次 则hash[4]8由此问题转变为 在hash中 我“偷”了某个下标i 获得了hash[i]分数 与i相邻的就不能偷了
4.1双状态数组
#include iostream
#include vector
using namespace std;int main()
{const int N 1e4 10;int hash[N] {0};int n 0;cin n;int per 0;int end 0;for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}vectorint f(end 1, 0);vectorint g(end 1, 0);for (int i 1; i end; i){f[i] g[i - 1] hash[i];g[i] max(f[i - 1], g[i - 1]);}cout max(f[end], g[end]) endl;return 0;
}4.2一维数组
#include iostream
#include vector
using namespace std;int main()
{int n 0;cin n;int per 0;int end 0;const int N 1e4 10;int hash[N] {0};for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}vectorint dp(end 1, 0);// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额dp[0] hash[0];dp[1] max(hash[0], hash[1]);for (int k 2; k end; k){dp[k] max(dp[k - 1], hash[k] dp[k - 2]);}cout dp[end] endl;return 0;
}4.3三变量法
#include iostream
#include vector
using namespace std;int main()
{const int N 1e4 10;int hash[N] {0};int n 0;cin n;int per 0;int end 0;for (int i 0; i n; i){cin per;end per end ? per : end;hash[per] per;}// 房子编号0~n-1// dp[k] 从0偷到k获得的最大金额int prv hash[0]; // dp[0]int cur max(hash[0], hash[1]); // dp[1]for (int i 2; i end; i){// dp[k] max(dp[k - 1], hash[k] dp[k - 2]);int tmp max(cur, hash[i] prv);prv cur;cur tmp;}cout cur endl;return 0;
}
