BATJ面试算法

第八课动态规划

70. 爬楼梯 class Solution { public: int climbStairs(int n) { std::vector<int> dp(n + 3, 0); dp[1] = 1; dp[2] = 1; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }; 198. 打家劫舍 class Solution { public: int rob(vector<int>& nums) { if (nums.size() == 0) { return 0; } if (nums.size() == 1) { return nums[0]; } //设第一个房间的最优解dp[i] std::vector<int> dp(nums.size(), 0); dp[0] = nums[0]; dp[1] = std::max(nums[0], nums[1]); for (int i = 2; i < nums.