DEV Community: Caixr

Brute force recursion to dynamic programming(knapsack problem) 03

Caixr — Sun, 26 Jun 2022 04:07:06 +0000

Question

Given two arrays of length N, w[] and v[], w[i] and v[i] represent the weight and values of item i, respectively. Given a positive number bag, representing a bag with a load bag. Your items cannot exceed this weight. Return what is the most value you can hold?

Solution #1 Brute force recursion

Found the base case, two cases, the array of w is end or bag capacity is less than zero. Because the weight of w[i] may be zero.
Decision, whether the w[i] position needs to be. If necessary, the bag capacity minus the weight of w[i] and add the value of v[i]. If not necessary, skip w[i] position. Choose the maximum of the two decisions.

public static int myMaxValue(int[] w, int[] v, int bag) {

        return myProcess(w, v, 0, bag);
    }

    public static int myProcess(int[] w, int[] v, int index, int bag) {
        if (bag < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }

        int p1 = myProcess(w, v, index + 1, bag);
        int p2 = 0;
        int next = myProcess(w, v, index + 1, bag - w[index]);
        if (next != -1) {
            p2 = next + v[index];
        }
        return Math.max(p1, p2);
    }

Solution #2 Dynamic programming

public static int myDp(int[] w, int[] v, int bag) {
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];

        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1) {
                    p2 = v[index] + dp[index + 1][rest - w[index]];
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }

        return dp[0][bag];
    }

Brute force recursion to dynamic programming(Dynamic Programming Attempt Models on Scope) 02

Caixr — Sat, 25 Jun 2022 09:13:44 +0000

Topic

Given an integer array, the cards representing differeent values are arranged in a line.Player A and Player B take each card in turn.It is stipulated that player A takes it first, and player B takes it later. But each player can only take the leftmost or rightmost card at time.Both Player A and Player B are extremely smart.Please return the score of the final winner.

Solution #1 Brute force recursion

Determine the parameters, palyers can choose a card from the [L-R] range of array, and only select cards in the [L] or [R] position.
Find base case. Palyer A takes cards first, when L == R, it means that there is only one card left, and player A can take it directly. Palyer B takes cards later, when L == R, it means that there are no cards left.
Player A can only take the leftmost or rightmost card at time and need to judge the best way to take the next card. Select the one with the best result out of two.

public static int myWin1(int[] arr) {
        int first = myF1(arr, 0, arr.length - 1);
        int second = myG1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }

    public static int myF1(int[] arr, int L, int R) {
        // player A take cards first
        if (L == R) {
            return arr[L];
        }
        int p1 = arr[L] + myG1(arr, L + 1, R); // current select arr[L] and the range can be selected next is arr[L+1...R]
        int p2 = arr[R] + myG1(arr, L, R - 1);// current select arr[R] and the range can be selected next is arr[L...R-1]
        // select the max
        return Math.max(p1, p2);
    }

    private static int myG1(int[] arr, int L, int R) {
        // player B take cards later
        if (L == R) {
            return 0;
        }
        int p1 = myF1(arr, L + 1, R);// player A took the card in [L] position
        int p2 = myF1(arr, L, R - 1);// player A took the card in [R] position
        // return the min. means that player B took the largest card and left player A with the smallest.
        return Math.min(p1, p2);
    }

Solution #2 Memoized search

public static int myWin2(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = myF2(arr, 0, arr.length - 1, fmap, gmap);
        int second = myG2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }

    public static int myF2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {

        if (fmap[L][R] != -1) {
            return fmap[L][R];
        }
        int ans = 0;
        if (L == R) {
            ans = arr[L];
        } else {
            int p1 = arr[L] + myG2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + myG2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }

    private static int myG2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        if (gmap[L][R] != -1) {
            return gmap[L][R];
        }
        int ans = 0;
        if (L != R) {
            int p1 = myF2(arr, L + 1, R, fmap, gmap);
            int p2 = myF2(arr, L, R - 1, fmap, gmap);
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }

Solution #3 Dynamic programming

public static int myWin3(int[] arr) {
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
            int L = 0;
            int R = startCol;
            while (R < N) {
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

Brute force recursion to dynamic programming 01

Caixr — Sat, 25 Jun 2022 05:52:29 +0000

Topic 1

Suppose there are N positions in a row, denoted as 1~N, and N must be greater than or equal to 2.
The robot is at the M position in the row at the beginning(M must be one of 1~N).
If the robot comes to position 1, then the next step can only go to position 2 to the right.
If the robot comes to the N position, then the next step can only go to position N-1 to the left.
If the robot comes to the middle position, then then next step can go left or right.
How many ways are there to specify that the robot must take K steps and finnaly reach the P position(P is also one of 1~N).
Given four parameters N, M, K, P, returns the number of methods.

Solution #1 Brute force recursion

Base case: Only when K is zero and the current position of robot is the P position find one way.
Boundary conditions: When robot current position is 1. The next step can only go to the right. When robot current position is N. The next step can only go to the left.
Middle position: When robot in the any middle position. The next step can go left or right.

public static int myWays1(int N, int M, int P, int K) {
        return myProcess1(M, K, P, N);
    }
// cur: robot current position
// rest: remaining steps
// aim: target position
// N: position of 1~N
    public static int myProcess1(int cur, int rest, int aim, int N) {
        if (rest == 0) { // no steps 
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) { // current position is 1,go to right
            return myProcess1(cur + 1, rest - 1, aim, N);
        }
        if (cur == N) { // current position is N, go to left 
            return myProcess1(N - 1, rest - 1, aim, N);
        }
        // current position in any middle position, go to left or right
        return myProcess1(cur + 1, rest - 1, aim, N) + myProcess1(cur - 1, rest - 1, aim, N);
    }

Solution #2 Memoized search

In Solution #1, can be found that only cur and rest parameters are changing. It can be seen from the figure that there is a process of repeated calculation in Solution #1. So we can use a cache to put already calculation values.

public static int myWays2(int N, int start, int aim, int K) {
        // dp cache
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return myProcess2(start, K, aim, N, dp);
    }

    public static int myProcess2(int cur, int rest, int aim, int N, int[][] dp) {

        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = myProcess2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = myProcess2(cur + 1, rest - 1, aim, N, dp) + myProcess2(cur - 1, rest - 1, aim, N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

Solution #3 Dynamic programming

Prepare an N+1 * K+1 two-dimensional array. Rows indicate position, columns indicate remaining steps.
Find base case, when remaining steps is zero and the position is P, so set dp[P][0] = 1.
The first row depends on the [rest - 1] position of the next row.
The last row depends on the [rest - 1] position of previous row.
The middle row depends on the sum of [rest - 1] postition of previous and next row.
Return the result is dp[M][K].

    public static int myWays3(int N, int M, int P, int K) {
        int[][] dp = new int[N + 1][K + 1];
        dp[P][0] = 1;

        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }

        return dp[M][K];
    }

LeetCode problem #46 and #47 Permutations

Caixr — Sun, 19 Jun 2022 16:18:12 +0000

46 Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution #1

Select a number from any position in the nums array and put it into the ans array, and remove the number that has been selected by nums.
Repeat the first step until the nums array is empty.
complete a set of answers, need to restore the number in the nums taht has been removed, and restore the number in ans that has been selected.

class Solution {
       public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> ans = new ArrayList();
        List<Integer> num = new ArrayList();
        for(int n : nums){
            num.add(n);
        }
        f(num,ans,res);
        return res;
    }

    public static void f(List<Integer> nums,List<Integer> ans,List<List<Integer>> res){
        if(nums.isEmpty()){
            res.add(new ArrayList<>(ans));
        }else{
            for(int i = 0;i<nums.size();i++){
                int n = nums.get(i);
                nums.remove(i);
                ans.add(n);
                ArrayList<Integer> integers = new ArrayList<>(nums);
                f(integers,ans,res);
                nums.add(i,n);
                ans.remove(ans.size() - 1);
            }
        }
    }
}

Solution #2

The solution #2 is similar to solution #1. Solution #2 does not require additional to store the answers, just swap the positions of the numbers in nums. Until the end of the nums array.

class Solution {
        public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        f(nums,0,res);
        return res;
    }

    public void f(int[] nums,int index,List<List<Integer>> res){
        if(index == nums.length){
            List<Integer> ans = new ArrayList();
            for(int i=0;i<nums.length;i++){
                ans.add(nums[i]);
            }
            res.add(ans);
        }else{
            for(int i=index;i<nums.length;i++){
                swap(nums,index,i);
                f(nums,index + 1,res);
                swap(nums,index,i);
            }
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

47. Permutations II

This question is an advanced level of "46.permutations". Asked to return the complete permutation that is not repeated.

Solution

Same solution as the previous question. Just add a set collection to record the numbers that has been visited.

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        f(nums,0,res);
        return res;
    }


    public void f(int[] nums,int index,List<List<Integer>> res){
        if(index == nums.length){
            List<Integer> ans = new ArrayList();
            for(int i=0;i<nums.length;i++){
                ans.add(nums[i]);
            }
            res.add(ans);
        }else{
            Set<Integer> vis = new HashSet();
            for(int i=index;i<nums.length;i++){
                if(!vis.contains(nums[i])){
                    vis.add(nums[i]);
                    swap(nums,index,i);
                    f(nums,index + 1,res);
                    swap(nums,index,i);
                }
            }
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}