动态规划

算法 动态规划

简单介绍

动态规划是利用存储历史信息使得未来需要历史信息时不需要重新计算， 从而达到降低时间复杂度，用空间复杂度换取时间复杂度目的的方法。

一般步骤

1.确定递推量，这一步需要确定递推过程中要保留的历史信息数量和具体含义，同时也定下动态规划的维度。（一般最难）

2.推导递推式，根据确定的递推量，得到如何利用存储的历史信息在有效时间(通常是常量或者线性时间)内得到当前的信息结果。

3.计算初始条件。一般初始条件是比较简单的情况，直接赋值即可。

4.（可选）考虑存储历史信息的空间维度。

例题分析

一维动态规划:

1. Climbing Stairs

   int climbStairs(int n) {
       int result = 0;
       int a = 1,b = 2;
       if(1 == n) return 1;
       if(2 == n) return 2;
   
       for (int i = 3; i<= n; i++)
       {
           result = a + b;
           a = b;
           b = result;
       }
       return result;
   }
   

2. Maximum Subarray

   int maxSubArray(vector<int>& nums) {
   
       if(nums.empty()) return 0;
   
       int result = nums[0];
       int cur_max = result;
       for(int i = 1;i < nums.size();i++)
       {
           // if(cur_max > 0) {
           //     cur_max += nums[i];
           // } else {
           //     cur_max = nums[i];
           // }
           cur_max = max(cur_max + nums[i], nums[i]);
           if(cur_max > result) result = cur_max;
   
       }
       return result;
   }
   

3. Maximum Product Subarray

   int maxProduct(vector<int>& nums) {
       if(nums.empty()) return 0;
   
       int result = nums[0];
       int cur_max = nums[0];
       int cur_min = nums[0];
       for(int i = 1;i < nums.size(); i++)
       {
           int temp = cur_max;
           cur_max = max(max(cur_max*nums[i],nums[i]),cur_min*nums[i]);
           cur_min = min(min(temp*nums[i],nums[i]),cur_min*nums[i]);
   
           if(cur_max > result) result = cur_max;
       }
       return result;
   }
   

4. Best Time to Buy and Sell Stock

   int maxProfit(vector<int>& prices) {
       if (prices.empty()) return 0;
   
       int result = 0;
       int cur_min = prices[0];
   
       for(int i = 1;i < prices.size();i++)
       {
           if(prices[i] - cur_min > result)
           {
               result = prices[i] - cur_min;
           }
   
           if(prices[i] < cur_min)
           {
               cur_min = prices[i];
           }
       }
       return result;
   }
   

5. Decode Ways

6. Unique Binary Search Trees

二维动态规划:

1. Edit Distance

   dp[i][j]代表word1[0...i]到word2[0...i]的最小编辑距离

   dp[i][0] = i;
   dp[0][j] = j;
   word1[i] = word2[j] dp[i][j] = d[i-1][j-1]
   word1[i] != word2[j]
   替换word1[i]为word2[j]: dp[i][j] = d[i-1][j-1]+1
   插入: dp[i][j] = d[i][j-1]+1, dp[i][j] = d[i-1][j]+1

   int minDistance(string word1, string word2) {
   int size1 = word1.size();
   int size2 = word2.size();
   
   if(0 == size1) return size2;
   if(0 == size2) return size1;
   int dp[size1+1][size2+1];
   
   for(int i = 0;i <= size1; i++)
      dp[i][0] = i; 
   for(int i = 0;i <= size2; i++)
      dp[0][i] = i;
   
   for(int i = 1; i <= size1; i++)
   {
       for(int j = 1;j <= size2; j++)
       {
           if(word1[i-1]==word2[j-1])
           {
               dp[i][j] = dp[i-1][j-1];
           } else {
               dp[i][j] = min(min(dp[i-1][j-1]+1,dp[i][j-1]+1),dp[i-1][j]+1);
           }
       }
   }
   
   return dp[size1][size2];
   
   }
   
   int minDistance(string word1, string word2) {
   int size1 = word1.size();
   int size2 = word2.size();
   
   if(0 == size1) return size2;
   if(0 == size2) return size1;
   
   int dp[size2+1];
   for(int i = 0; i <= size2; i++)
   {
       dp[i] = i;
   }
   
   for(int i = 1; i <= size1; i++)
   {
       int dp_temp[size2+1];
       dp_temp[0] = i;
       for(int j = 1;j <= size2; j++)
       {
           if(word1[i-1] == word2[j-1])
           {
               dp_temp[j] = dp[j-1];
           } else {
               dp_temp[j] = min(min(dp[j-1]+1,dp[j]+1),dp_temp[j-1]+1);
           }
       }
       for(int k = 0; k <= size2; k++)
       {
           dp[k] = dp_temp[k];
       }
   }        
   return dp[size2];
   

   }