1049. Last Stone Weight II

Oct. 9, 2019

Introduction

It is my second practice. I like to write one more idea and also look into the issues, what I should learn from the code.

Case study

Here is the post.

Oct. 9, 2019
It is a good idea to learn to write more than one solution. What I did is to study the most popular post in the discussion post, and then I wrote one C# solution.

It is important to read the case study I prepare first, and then it will be much easy to follow the design of the solution.

Case study
Given the array with values [31, 26, 33, 21, 40], the sum of the array is 151, let us denote it as Sum. Sum/ 2 will be 75. We can divide into two sets, [33, 40] and [31, 26, 21], the sum of first array is 73, and the sum of second array is 78, the minimum difference is 5.

But if we update the loop from ascending (this is descending, (for (int i = Math.Min(1500, prefixSum); i >= item; i--)), one number may be used more than once, so that minimum difference can be one. Since [26, 26, 23] can be an array, but 26 is counted twice, the sum of the array is 75, so 151 - 2 * 75 = 1.

The challenges

1. How to design the solution so that each stone will be at most counted once to the sum?
2. Argue to yourself, why order does not matter? We can count each stone at most once in any sum, but which goes first does not matter.

Here are highlights:

1. Understand how to convert the problem to classical Knapsack problem to divide array into two sets;
2. Understand how to find all possible sum using all stones available, make sure that one stone can only be used at most once for each sum;
3. Most challenging problem is to design the search using descending order. Detail see my first practice if you have questions. Here is the post.
4. Go over a test case and learn the case study before working on the solution.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1049_last_stone_weight_II___lee215
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// Oct. 9, 2019
        /// study code
        /// https://leetcode.com/problems/last-stone-weight-ii/discuss/294888/JavaC%2B%2BPython-Easy-Knapsacks-DP
        /// 
        /// The idea is to implement the solution using time complexity O(NS), N is length of the array, S is the sum of the array. 
        /// space complexity is O(S), where S = sum of the array stones. 
        /// </summary>
        /// <param name="stones"></param>
        /// <returns></returns>
        public static int LastStoneWeightII(int[] stones)
        {
            // length <= 30, value of stones [1, 100]
            var dp = new bool[1501];

            dp[0] = true;
            var sum = stones.Sum();

            var prefixSum = 0; 

            foreach (var item in stones)
            {
                prefixSum += item;
                for (int i = Math.Min(1500, prefixSum); i >= item; i--)
                {
                    dp[i] |= dp[i - item];
                }
            }

            for(int i = sum/2; i > 0; i--)
            {
                if(dp[i])
                {
                    return sum - i * 2; 
                }
            }

            return 0; 
        }
    }
}