A Code

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 minimumNumberofRefuelingStops ( int target, int startFuel, vector < vector < int >> &stations) { // Write your code here. //这题还是很难的，知道用DP，但不知道怎么定义state。想了想，怎么定义state都解释不通。 //还是解法思想，看了答案，定义state为停i次，油箱中一共加了多少油。 const int size = stations.size(); if (size == 0 ){ if (startFuel >= target){ return 0 ; } else { return -1 ; } } vector < long > dp(size + 1 , startFuel); dp[ 0 ] = startFuel; for ( int k = 0 ; k < size; k++){ //这里顺序反了就不对了。k在外还是i在外？看实际逻辑吧，要在实际 //物理意义中找到答案 for ( int i = 0 ; i <= k; i++){ if (dp[i] >= stations[k][ 0 ]){ dp[i + 1 ] = max(dp[i + 1 ], dp[i] + stations[k][ 1 ]); } } } for ( int i = 0 ; i <= size; i++){ if (dp[i] >= target){ ...

class Solution { public : /** * @param arr: the array of bottles * @return: the minimum number of times you can take all the bottles */ int takeAwayTheBottle ( vector < int > &arr) { // Write your code here. // search longest palidrome sub sequence. // 居然是DP，感觉没有道理的DP. // 看了凡是涉及substr，subseq,又是最大最小，或个数就先考虑DP。这是一个可能方向,虽然开始 // 会理不清DP的转移，但往这个方向分析，定义了状态的物理意义就可能明显些了。 // dp[i][j]: index i和j之间的最小次数。 // transition: // 1) arr[i] == arr[j]: dp[i][j] = dp[i + 1][j - 1]; // 2) else: (往前遍历) k = j - 1,....,i: min(dp[i][k] + dp[k + 1][j]) 最小值。 // result: dp[0][size - 1]; const int size = arr.size(); if (size <= 1 ){ return size; } vector < vector < int >> dp(size, vector < int >(size, INT_MAX)); for ( int i = 0 ; i < size; i++){ dp[i][i] = 1 ; } for ( in...

DP version: class Solution { public:     int maxTurbulenceSize(vector<int>& A) {         const int size = A.size();         if(size < 2){             return size;         }         vector<int> dp(size, 1);         dp[0] = 1;         int res = 1;         for(int i = 0; i < size - 1; i++){             if(i % 2 == 0){                 if(A[i] > A[i + 1]){                     dp[i + 1] = dp[i] + 1;                 }             }             else{                 if(A[i] < A[i + 1]){         ...

class Solution { public : /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum ( vector < vector < int >> &grid) { // write your code here // DP const int m = grid.size(); if (m == 0 ){ return 0 ; } const int n = grid[ 0 ].size(); //vector<vector<int>> dp(m, vector<int>(n, 0)); //vector<vector<int>> dp(2, vector<int>(n, INT_MAX)); vector < int > dp(n, INT_MAX); dp[ 0 ] = 0 ; //dp[0][0] = grid[0][0]; //for(int i = 1; i < m; i++){ // dp[i][0] = dp[i - 1][0] + grid[i][0]; //} //for(int j = 1; j < n; j++){ // dp[0][j] = dp[0][j - 1] + grid[0][j]; //} for ( int i = 0 ; i < m; i++){ for ( int j = 0 ; j < n; j++){ ...

class Solution { public : /** * @param A: an array * @param K: an integer * @return: the largest score */ double largestSumOfAverages ( vector < int > &A, int K) { // Write your code here //DP const int size = A.size(); if (size == 0 ){ return 0 ; } vector < double > prefixSum(size + 1 , 0 ); for ( int i = 1 ; i <= size; i++){ prefixSum[i] = prefixSum[i - 1 ] + A[i - 1 ]; } if (K >= size){ return prefixSum[size]; } if (K == 1 ){ return prefixSum[size] / size; } vector < vector < double >> dp(K + 1 , vector < double >(size + 1 )); for ( int i = 1 ; i <= size; i++){ dp[ 1 ][i] = prefixSum[i] / i; } for ( int i = 2 ; i <= K; i++){ for ( int j = i; j <= size; j++){ ...

Code ( Language :C++) ( Judger :cloudjudge-cluster-5) Edit class Solution { public : /** * @param values: a vector of integers * @return: a boolean which equals to true if the first player will win */ bool firstWillWin ( vector < int > &values) { // write your code here // 这个DP有些不一般。 // 1,从后往前。 // 2,博弈 const int size = values.size(); if (size <= 2 ){ return true ; } int sum = 0 ; for ( auto i : values){ sum += i; } vector < int > dp(size, 0 ); // 从该index开始能取得最大值。 dp[size - 1 ] = values[size - 1 ]; dp[size - 2 ] = values[size - 2 ] + values[size - 1 ]; dp[size - 3 ] = values[size - 3 ] + values[size - 2 ]; for ( int i = size - 4 ; i >= 0 ; i--){ // pick one int pick1 = values[i] + min(dp[i + 2 ], dp[i + 3 ]); int pick2 = 0 ; ...