面试中一些简单的动态规划浅谈(上)

前导技能：

递归，暴搜

本质: 递归

原问题->子问题->原问题

最有子结构:

　　子问题最优决策可导出原问题最优决策

　　无后效性

重叠子问题:

　　去冗余

　　空间换时间

Leetcode198

链接：https://leetcode.com/problems/house-robber/

题意：要去抢n家店，相邻的两家不能抢，问怎么样才能使抢来的钱最高

分析：对于idx家店，如果我们抢了，则后面只能从idx-2开始计算了，否则可以从idx-1开始计算，取二者的最大值即位所求

 1 class Solution {
 2 public:
 3     int solve(vector<int> nums,int idx){
 4         if(idx<0){
 5             return 0;
 6         }
 7         return max(nums[idx]+solve(nums,idx-2),solve(nums,idx-1));
 8     }
 9     int rob(vector<int>& nums) {
10         int n=num.size();
11         return solve(nums,n-1);
12     }
13 };

暴搜代码

 1 class Solution {
 2 public:
 3     int dp[10010];
 4     int solve(vector<int> nums,int idx){
 5         if(idx<0){
 6             return 0;
 7         }
 8         if(dp[idx]>=0){
 9             return dp[idx];
10         }
11         dp[idx]=max(nums[idx]+solve(nums,idx-2),solve(nums,idx-1));
12         return dp[idx];
13     }
14     int rob(vector<int>& nums) {
15         memset(dp,-1,sizeof(dp));
16         int n=nums.size();
17         return solve(nums,n-1);
18     }
19 };

AC Code