1. Climbing Stairs

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/569/

Dynamic Programming:

(There are also other methods exists such as recursion, but only apply DP this time)

  1. class Solution { 
  2. public:
  3.     int climbStairs(int n) { //basically a fibonacci
  4.         if(n == 1)
  5.             return 1;
  7.         int curr = 1;
  8.         int prev = 0;
  9.         int next = 1;
  11.         for(int i = 0; i < n; i++){
  12.             curr = prev + next;
  13.             prev = next;
  14.             next = curr;
  15.         }
  17.         return curr;
  18.     }
  19. };

2. Best Time to Buy and Sell Stock

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/572/

Dynamic Programming:

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) { //break the problem into
  4.                                          //1. find the minimum value and
  5.                                              //2. find the maximum profit that related to the minimum value
  6.         int min_val = INT_MAX;
  7.         int max_pro = 0;
  9.         for(int i = 0; i < prices.size(); i++){
  10.             if(prices[i] < min_val)
  11.                 min_val = prices[i];
  13.             if((prices[i] - min_val) > max_pro)
  14.                 max_pro = prices[i] - min_val;
  15.         }
  17.         return max_pro;
  18.     }
  19. };

3. Maximum Subarray

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/566/

Dynamic Programming:

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) { 
  4.         if(nums.size()==1)
  5.             return nums[0];
  7.         int max_sum = nums[0];
  8.         int cur_sum = 0;
  9.         int n = nums.size();
  11.         for(int i = 0; i < n; i++){
  12.             cur_sum += nums[i];
  14.             max_sum = max(max_sum, cur_sum);
  15.             //update the maximum sum
  17.             cur_sum = max(cur_sum, 0);
  18.             //we only need the maximum sum in subarrays, so this is a kind of reset if the sum is negative
  19.             //if cur_sum >= 0, the array before is worthy to be added
  20.         }
  22.         return max_sum;
  23.     }
  24. };

4. Horse Robber

https://leetcode.com/problems/house-robber/