Блог

решение последнего камня весом 2 в cpp

Это позволяет пройти все тестовые случаи.

 class Solution {
   public:
   int lastStoneWeightII(vector<int>amp; stones) {
      int n = stones.size();
      int total = 0;
      for(int i = 0; i < n; i  ){
         total  = stones[i];
      }
      int req = total / 2;
      vector <bool> dp(req   1, false);
      dp[0] = true;
      int reach = 0;
      for(int i = 0; i < n; i  ){
         for(int j = req; j - stones[i] >= 0; j--){
            dp[j] = dp[j] || dp[j - stones[i]];
            if(dp[j]) reach = max(reach, j);
         }
      }
      return total - (2 * reach);
   }
};
  

Я попытался воспроизвести его в javascript и не смог передать
простые тестовые примеры, такие как [2,7,4,1,8,1]

Вот моя попытка

 var lastStoneWeightII = function(st) {
    // stone #
    const n = st.length;
    // sum up
    const sum = st.reduce((acc, curr) => {return acc curr});
    // e.g. half
    const ha = Math.floor(sum / 2);
    
    // half 1
    const dp = Array(ha 1).fill(false);
    // 1st ele = true
    dp[0] = true;
   
    // store tmp_max
    let max = 0;
    // loop element
    for(let i=0; i<n; i  ) {
        // single element
        const w = n[i];
        // backward, half
        for(let j=ha; j-w>=0; j--) {
            // update condi
            dp[j] = dp[j] || dp[j-w]; 
                
            // never comes in
            if(dp[j]) {
                //test
                console.log('     max', max, 'j', j)
                max = Math.max(max, j);
            }
        }
    }
    
    return (sum - max) - max;
}