文章目录
原题题目
代码实现（首刷自解）
代码实现（二刷DAY 93 C++ 自解）
代码实现（三刷自解 DAY 157 C++)
代码实现（四刷自解 DAY 243 C++）
代码实现（五刷自解 DAY 295 C++）
代码实现（五刷自解 含输出路径 DAY 295 C++）
代码实现（六刷自解 DAY 9 Golang）
原题题目
代码实现（首刷自解）
int rob ( int * nums, int numsSize) {
int dp[ 101 ] = {
0 } , i, max = 0 ; dp[ 0 ] = 0 ; for ( i= 1 ; i<= numsSize; i++ ) {
dp[ i] = nums[ i- 1 ] ; if ( i >= 3 ) dp[ i] += fmax ( dp[ i- 2 ] , dp[ i- 3 ] ) ; if ( dp[ i] > max) max = dp[ i] ; } return max;
}
代码实现（二刷DAY 93 C++ 自解）
class Solution {
public : int rob ( vector< int > & nums) {
int ret = - 1 , size = nums. size ( ) ; vector< int > dp ( size+ 1 , 0 ) ; for ( int i= 0 ; i< size; ++ i) {
dp[ i] = nums[ i] ; if ( i== 1 ) dp[ i] = max ( dp[ i] , dp[ i- 1 ] ) ; if ( i>= 2 ) dp[ i] = max ( dp[ i- 2 ] + nums[ i] , dp[ i- 1 ] ) ; ret = max ( ret, dp[ i] ) ; } return ret; }
} ;
代码实现（三刷自解 DAY 157 C++)
class Solution {
public : int rob ( vector< int > & nums) {
if ( nums. size ( ) == 1 ) return nums[ 0 ] ; for ( int i= 2 ; i< nums. size ( ) ; ++ i) {
if ( i == 2 ) nums[ i] += nums[ 0 ] ; else nums[ i] += max ( nums[ i- 2 ] , nums[ i- 3 ] ) ; } return max ( nums[ nums. size ( ) - 1 ] , nums[ nums. size ( ) - 2 ] ) ; }
} ;
代码实现（四刷自解 DAY 243 C++）
class Solution {
public : int rob ( vector< int > & nums) {
int ans = 0 , size = nums. size ( ) ; vector< int > dp ( size, 0 ) ; for ( int i = 0 ; i < size; ++ i) {
dp[ i] = max ( ( i >= 2 ? dp[ i - 2 ] : 0 ) + nums[ i] , ( i >= 1 ? dp[ i - 1 ] : 0 ) ) ; ans = max ( ans, dp[ i] ) ; } return ans; }
} ;
代码实现（五刷自解 DAY 295 C++）
class Solution {
public : int rob ( vector< int > & nums) {
vector< int > dp ( nums. size ( ) , 0 ) ; int ret = nums[ 0 ] ; dp[ 0 ] = nums[ 0 ] ; if ( nums. size ( ) >= 2 ) {
ret = max ( ret, nums[ 1 ] ) ; dp[ 1 ] = ret; } for ( int i = 2 ; i < dp. size ( ) ; ++ i) {
dp[ i] = max ( dp[ i - 2 ] + nums[ i] , dp[ i - 1 ] ) ; ret = max ( ret, dp[ i] ) ; } return ret; }
} ;
代码实现（五刷自解 含输出路径 DAY 295 C++）
class Solution {
public : int rob ( vector< int > & nums) {
vector< pair< int , int >> dp ( nums. size ( ) ) ; int ret = nums[ 0 ] ; dp[ 0 ] . first = nums[ 0 ] ; dp[ 0 ] . second = - 1 ; if ( nums. size ( ) >= 2 ) {
if ( nums[ 1 ] > nums[ 0 ] ) {
dp[ 1 ] . first = nums[ 1 ] ; dp[ 1 ] . second = - 1 ; } else {
dp[ 1 ] . first = nums[ 0 ] ; dp[ 1 ] . second = - 1 ; } } for ( int i = 2 ; i < dp. size ( ) ; ++ i) {
if ( dp[ i - 2 ] . first + nums[ i] > dp[ i - 1 ] . first) {
dp[ i] . first = dp[ i - 2 ] . first + nums[ i] ; dp[ i] . second = i - 2 ; } else {
dp[ i] . first = dp[ i - 1 ] . first; dp[ i] . second = i - 1 ; } ret = max ( ret, dp[ i] . first) ; } int pos = dp. size ( ) - 1 ; while ( pos != - 1 ) {
int nextpos = dp[ pos] . second; if ( ! nums[ pos] || nextpos == - 1 || dp[ pos] . first != dp[ nextpos] . first) {
cout << nums[ pos] << " -> " ; } pos = nextpos; } return ret; }
} ;
代码实现（六刷自解 DAY 9 Golang）
func max ( x, y int ) int {
if x >= y {
return x} else {
return y}
} func rob ( nums [ ] int ) int {
if len ( nums) == 1 {
return nums[ 0 ] } if len ( nums) == 2 {
return max ( nums[ 0 ] , nums[ 1 ] ) } pre1, pre2 := nums[ 1 ] , nums[ 0 ] now := max ( pre1, pre2) for i := 2 ; i < len ( nums) ; i++ {
now = max ( pre2 + nums[ i] , pre1) pre2, pre1 = max ( pre2, pre1) , now} return now
}
