C++：动态规划记忆化

解题思路:

你如果问我动态规划记忆化和普通的递归函数+vector容器有什么区别

那我会说动态规划记忆化就是能计算一次解决问题的，不要计算两次，普通的是存在重复计算的(*-*  )

注意事项:

参考代码:

#include<iostream>

#include<vector>

using namespace std ;

int ko ( int n , vector<int>&v )

{

         if ( n == 0 )

        //为什么这里是n==0 ，因为这里vector容器下标范围是[ 0, n-1 ]

         {

                 v[n] = 1 ;

                 return 1 ;

         } 

         else if ( n == 1 )

         {

                 v[n] = 1 ;

                 v[n-1] = 1 ;

                 return 1 ;

         }

         if ( v[n] != 0 ) return v[n] ;

         else 

         {

                 if ( v[n-1] == 0 ) 

                 {

                         v[n-1] = ko ( n-1 , v ) ;

                 }

                 else if ( v[n-2] == 0 )

                 {

                         v[n-2] = ko ( n-2 , v ) ;

                 }

                 v[n] = v[n-1] + v[n-2] ;

                 return v[n] ;

         }

}

int main ( )

{

         int n = 0 ;

         cin >> n ;

         vector<int> v ( n , 0 ) ;

         ko ( n-1 , v ) ;

 //为什么这里是n-1 ，因为这里vector容器下标范围是[ 0, n-1 ] 

         for ( int i = 0 ; i < n ; i ++ )

         {

                  cout << v[i] << " " ;

         }

         cout << endl ;

         return 0 ;

}