动态规划 -- 打家劫舍

打家劫舍你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例 输入[1,2,3,1]输出4解释偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3偷窃到的最高金额 1 3 4。动规方程dp[i] max( dp[i-1] , dp[i-2] ar[i] );代码编写1.0动态规划求解int rob1(const std::vectorint ar){ int lenar.size(); if(len 0)return 0; if(len 1)return ar[0]; vectorint dp(len1,0); dp[0]0; dp[1]ar[0]; for(int i2;ilen;i){ dp[i]std::max(dp[i-1],dp[i-2]ar[i-1]); } return dp[len]; }2.0空间优化用两个变量precur代替数组int rob2(const std::vectorint ar) { int len ar.size(); if (len 0) return 0; if (len 1) return ar[0]; //vectorint dp(len 1, 0); int pre 0; int cur ar[0]; for (int i 2; i len; i){ int tmp std::max(cur, pre ar[i - 1]); pre cur; cur tmp; } return cur; } ​3.0穷举所有合法的偷窃方案子集树 回溯-- 不仅求最大值还能记录偷窃路径class Rob { std::vectorint ar; // 每间房子的钱 std::vectorint cur;// 当前方案cur[i]1 表示偷第i间0不偷 std::vectorint vcur;// 最优方案 ​ int len; // 房子总数 int maxsum; // 能偷的最大金额 int cursum; // 当前正在尝试的方案总金额 ​ static void PrintVec(const std::vectorint a){ int n a.size(); for (int i 0; i n; i){ printf(%5d, a[i]); } printf(\n----------------------\n); } void MaxRob(int i, int n) { if (i n){ if (cursum maxsum){ maxsum cursum; vcur cur; } } else{ // 选择 1偷第 i 间前提i0第一间 或 前一间没偷 if (i 0 || cur[i-1] 0 ){ cur[i] 1; // 标记为偷 cursum ar[i]; // 累加金额 MaxRob(i 1, n); // 继续处理下一间 // 回溯撤销选择恢复状态 cursum - ar[i]; cur[i] 0; } // 选择 2不偷第 i 间直接处理下一间 MaxRob(i 1, n); } } public: Rob(const std::vectorint nums){ len nums.size(); ar nums; // 保存房子金额 cur.resize(len, 0); // 初始化标记数组全不偷 maxsum 0; // 最大金额初始0 cursum 0; // 当前金额初始0 } ​ int maxSum(){ if (len 0) return 0; if (len 1) return ar[0]; MaxRob(0, len); return maxsum; } void Print() const{ for (auto x : vcur) { printf(%5d, x); } printf(\n---------------\n); } };