A Code

vector < int > asteroidCollision( vector < int > &asteroids) { // write your code here vector < int > res; for ( int i = 0 ; i < asteroids.size(); ++i) { if (asteroids[i] > 0 ) { res.push_back(asteroids[i]); } else { // less than 0 if (res.empty() || res.back() < 0 ) { res.push_back(asteroids[i]); } else if (res.back() <= -asteroids[i]) { if (res.back() < -asteroids[i]) { --i; } res.pop_back(); } } } return res; }

背包分类： 1，元素不重复使用。（backpack I, II, V） 2，元素重复使用 ：计算多少可能时又分1）不同order对应不同可能情况 2）相同的元素不同order对应一种可能情况。 2 -1) backpack VI 2-2) backpack IV(和coin 2一样) 背包所有问题都开始用二维DP state来表示，i是元素index，j是容量index。dp[i][j]表示给出前i元素和容量是j时，对应的结果。 优化空间，即优化成一维DP state，只保留j容量index。 类型1和2-2）双层for循环，外层是元素index。内存的容量index要从右往左。原因是，一维状态是模拟二维状态，当前的更新是根据上一行的结果来进行，所以从右往左，否则，左边的值先变了，再用来更新右边的值就错了。 类型2-1），双层for循环，外层是容量index，内层是元素index。都从左往右。

int backPackVI ( vector < int > &nums, int target) { // write your code here const int size = nums.size(); vector < int > dp(target + 1 , 0 ); dp[ 0 ] = 1 ; //for(int j = target; j >= nums[i]; j--){ for ( int j = 1 ; j <= target; j++){ for ( int i = 0 ; i < size; i++){ if (j >= nums[i]){ dp[j] += dp[j - nums[i]]; } } } return dp[target]; } 元素重复使用多次

int backPack ( int m, vector < int > &A) { // write your code here vector < bool > dp(m + 1 , 0 ); dp[ 0 ] = true ; for ( int i = 0 ; i < A.size(); i++){ for ( int j = m; j >= A[i]; j--){ dp[j] = dp[j] || dp[j - A[i]]; } } for ( int j = m; j >= 0 ; j--){ if (dp[j]){ return j; } } }

int backPackII ( int m, vector < int > &A, vector < int > &V) { // write your code here // dp[i][j]: max value with i packsize and first j elements; // transition: 能放：1）放 2）不放 -> max(dp[i][j - 1], dp[i - A[j - 1]][j - 1] + V[j - 1]) // 不能放：dp[i][j] = dp[i][j - 1] // initial : dp[0][0] = 0; const int size = A.size(); vector < vector < int >> dp(m + 1 , vector < int >(size + 1 , 0 )); for ( int i = 1 ; i <= m; i++){ for ( int j = 1 ; j <= size; j++){ if (i >= A[j - 1 ]){ dp[i][j] = max(dp[i][j - 1 ], dp[i - A[j - 1 ]][j - 1 ] + V[j - 1 ]); } else { dp[i][j] = dp[i][j - 1 ]; } } } return dp[m][size]; } 优化成一维数组 /为什么从右往左？把原来的二维看成矩阵，每次更新都是基于上一行的结果， 所以在一维下，要从右往左，这样用于更新的值相当于是上一次的结果。如果从左往右，左边的值都变了。 ...

int backPackIV ( vector < int > &nums, int target) { // write your code here const int size = nums.size(); if (size == 0 ){ return 0 ; } vector < int > dp(target + 1 , 0 ); dp[ 0 ] = 1 ; for ( auto a : nums){ for ( int i = a; i <= target; i++){ dp[i] += dp[i - a]; } } return dp[target]; }

int backPackV ( vector < int > &nums, int target) { // write your code here // 和coins不同之处是，这里每个元素只能用一次 const int size = nums.size(); if (size == 0 || target == 0 ){ return 0 ; } vector < vector < int >> dp(target + 1 , vector < int >(size + 1 , 0 )); dp[ 0 ][ 0 ] = 1 ; for ( int j = 1 ; j <= size; j++){ dp[ 0 ][j] = 1 ; } for ( int i = 1 ; i <= target; i++){ for ( int j = 1 ; j <= size; j++){ if (i >= nums[j - 1 ]){ dp[i][j] = dp[i - nums[j - 1 ]][j - 1 ] + dp[i][j - 1 ]; //这里是和coin change不一样的地方，dp[i - nums[j - 1]][j] //其实就可以转成一维数组了。[j]只和之前的j - 1有关。 } else { dp[i][j] = dp[i][j - 1 ]; } } } return dp[target][size]; }

int change ( int amount, vector < int > &coins) { // write your code here // DP state: DP[i][j] the number of combinations regarding to the amount of i given first j coins. (It does not mean the j-th element must be used) // transition: if(coins[j] <= i) dp[i] = dp[i - coins[j - 1]][j] + dp[i][j - 1]; //可重复使用 // // int coinChange(vector<int> &coins, int amount) { // write your code here const int size = coins.size(); if (size == 0 ){ return 0 ; } if (amount == 0 ){ return 0 ; } vector < vector < int >> dp(amount + 1 , vector < int >(size + 1 , 0 )); dp[ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= amount; i++){ for ( int j = 1 ; j <= size; j++){ dp[ 0 ][j] = 1 ; // if (i >= coins[j - 1 ]){ //int tmp = ; ...