【算法】详解动态规划

class Solution { public: int Fibonacci(int n) { if(n<=0) return 0; if(n == 1 || n == 2) return 1; return Fibonacci(n-1)+Fibonacci(n-2); } }; 

class Solution { public: int Fibonacci(int n) { //先申请一个空间来保存解 vector 
  
    f(n + 1, 0); //初始化 f[0] = 0; if (n <= 0) return f[0]; f[1] = 1; if (n == 1) return f[1]; f[2] = 1; //状态递推 for (int i = 3; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } //返回结果 return f[n]; } }; 
  

class Solution { public: int Fibonacci(int n) { if (n <= 0) return 0; if(n == 1 || n == 2) return 1; //初始化 int fn1 = 0; int fn2 = 1; int result = 0; for (int i = 2; i <= n; i++) { //递推公式 result = fn1 + fn2; fn1 = fn2; fn2 = result; } //返回结果 return result; } }; 

class Solution { public: int jumpFloorII(int number) { if (number <= 0) return 0; //初始化 int total = 1; for (int i = 1; i < number; i++) { //递推 total = 2 * total; } //返回结果 return total; } }; 

class Solution { public: int rectCover(int number) { if (number <= 0) return 0; if (number == 1) return 1; if (number == 2) return 2; vector 
  
    f(number + 1, 0); //初始化 f[0] = 0; f[1] = 1; f[2] = 2; for (int i = 3; i <= number; i++) { //状态递推 f[i] = f[i - 1] + f[i - 2]; } //返回结果 return f[number]; } }; 
  

给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。

class MaxSum { public: int getMaxSum(vector 
  
    A, int n) { // write code here if (A.empty()) return 0; vector 
   
     f(A.size(), 0); //初始化 f[0] = A[0]; for (int i = 1; i < A.size(); i++) { //状态递推 f[i] = max(f[i - 1] + A[i], A[i]); } //输出结果 int result = A[0]; for (int i = 0; i < A.size(); i++) { result = max(f[i], result); } return result; } }; 
    
  

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

class Solution { public: bool wordBreak(string s, unordered_set 
  
    &dict) { if (s.empty() || dict.empty()) return false; int n = s.size(); vector 
   
     can_break(n + 1, false); //初始化 can_break[0] = true; //递推 for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) { if (can_break[j] && dict.find(s.substr(j,i-j)) != dict.end()) { can_break[i] = true; break; } } return can_break[n]; } }; 
    
  

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

The minimum path sum from top to bottom is11(i.e., 2 + 3 + 5 + 1 = 11).

class Solution { public: int minimumTotal(vector 
  
    > &triangle) { if (triangle.empty()) return 0; vector 
   
     > min_sum(triangle); //初始化 min_sum[0][0] = triangle[0][0]; //递推 for (int i = 1; i < triangle.size(); i++) { for (int j = 0; j <= i; j++) { //左边界 if (j == 0) { min_sum[i][j] = min_sum[i - 1][j] + triangle[i][j]; } //右边界 else if (j == i) { min_sum[i][j] = min_sum[i - 1][j - 1] + triangle[i][j]; } //中间 else { min_sum[i][j] = min(min_sum[i - 1][j - 1], min_sum[i - 1][j]); min_sum[i][j] = min_sum[i][j] + triangle[i][j]; } } } int line = triangle.size(); int result = min_sum[line - 1][0]; for (int i = 1; i < line; i++) { result = min(result, min_sum[line - 1][i]); } //返回结果 return result; } };