Analyze Question

This is a simple example to understand matrix chain order in DP.
As we know, all the DP problem can be solve by three basic criteria

1. find the optimized sub problem

   In matrix multiplication , the cost of multiplication of matrix is different between the different multi sequence.for e.g. we have 3 matrix

   A: 10X100

   B: 100x5

   C: 5x50

   then if we follow diff multiplication sequence

   for ((A1A2)A3) : A1A2=$10\times 100 \times 5 = 5000 $ A3=$10\times5\times50 = 2500$ tot: 7500

   for(A1(A2A3)): A2A3=$100 \times 5 \times 50 = 25000$ A1 = $10\times100\times50=50000$ tot:75000

   and thus its 10 times bigger for the last approach than the first approach

   and in DP we suppose if we already know the best solution for the matrix multiplication, for e.g. (A1A2A3A4)(A5A6A7) , if we separate them into subarrays ((A1A2A3)A4) (A5(A6A7)) the subarray it self should also be the optimized multiplication.

举个栗子：

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Method:

The Huffman coding which implies the greedy algorithm has its theory:

If you have a set of characters , and called it $C$ , has several characters which may or may not overlap each other.

Then lets say $C$ contains these characters: f,e,d,c,b,a

each character has different frequency which we will called it $F$ . Now we have a sequence like: f(5) ,e(9), d(16), c(12),b(13),a(45)

Now if we want to code these characters in order to get a better compression of the space we stored it , we have two choices

1. we just simply code it into same length code
2. we use the greedy method, which means we do our best to put the higher frequency character into short codes and lower frequency characters into the longer codes

[Array] finding a number in 2D array

In a 2-D array (each sub-array has same length) every row is ascending from left to right

every col is ascending from up to down, find a number in this array, return a true/false to indicate found/not found

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public class Solution {
   public  boolean Find(int target, int[][] array) {
        if (array.length == 0 || array[0].length == 0) return false;
        int l = array.length - 1;
        int k = array[0].length - 1;
        if (target < array[0][0] || target > array[l][k]) return false;

        for (int i = 0; i <= l; i++) {
            if (array[i][0] > target) continue;
            if (search(target, i, 0, k, array)) return true;
        }

        return false;

    }


    private  boolean search(int target, int i, int min, int max, int[][] arr) {

        if (max >= min) {
            int mid = min+(max-min) / 2;
            if (target == arr[i][mid]) return true;

            if (arr[i][mid] > target) {
                return search(target, i, min, mid-1, arr);
            } else {
                return search(target, i, mid+1, max, arr);
            }
        }
        return false;

    }
}

simplest solution, to traverse trough the first col of array in $m$ time and run a binary search for each row. total time complexity is $mlogn$.