Bowen's Tech Blog
0%

Posted on Edited on In ,

Overview

Sometimes normal recursive method will cost a lot of time and not very efficient. In these cases, the DP(Dynamic Programming) can be a good choice. The key of DP is to record the previous solutions.

If a problem has two featrues:

  • Optimal Substructure
    • The solution of a problem depends on the solution of its subproblem
  • Overlapping subproblem
    • The subproblem needs to be used several times when dealing with the main problem
      Then we can think about using DP.

Two forms

There are two main ways to do DP. The bottom-up is the most common DP method.

Top-down(recursion with memory)

Establish a memory data structure(like a list) to store the previous values, avoiding the repeat calculation on that value.

Bottom-up(real DP)

Iterate from the bottom. This is better than the previous one because there is no recursive thus no extra cost.

Template

I felt DP is like a 2-demensional array, which can be reduced to a 1-D array. Usually the row i means the action at step i; the column j means a similar result to the original question.

1
2
3
4
5
6
dp = [[.. for i in range(m)] for j in range(n)] # Create 
dp[0][0] = ...    # init
for i in ...
    for j in ...
        dp[i][j] = ...	# transition
return dp[x][y]

Models

Linear Model

SubArray

dp[i] means subarray s[:i] and you must use s[i-1], return max(dp)

No.53 - Max sum subarray

1
2
3
4
5
if dp[i - 1] > 0:
    dp[i] = dp[i-1] + nums[i]
else:
    dp[i] = nums[i]
return max(dp)

No.300 - Longest Increasing Subsequence

No.152 - Maximum Product Subarray
dp1 contains the max product; dp2 contains the min product

List from 0 to i

dp[i] means s[:i], return dp[len(s)]

No.139 - Word Break

No.91 - Decode Ways

No.70 - Climbing Stairs

No.279 - Perfect Squares

No.62 - Unique Paths

Interval Model

The problem can be described as p[i, j]

Palindromic Substring

No.5 - Longest Palindromic Substring
dp[i][j] means wether s[i: j + 1] is a palindromic substring

1
2
3
4
5
6
7
8
9
for i in range(len(s)):
    dp[i][i] = True

for i in range(len(s), -1, -1):
    for j in range(i, len(s)):
        if i + 1 > j - 1:
            dp[i][j] = dp[i][j] or s[i] == s[j]
        else:
            dp[i][j] = dp[i][j] or dp[i + 1][j - 1] and s[i] == s[j] 
1
2
3
4
5
6
7
8
9
10
11
12
13
# This function will recursively check the left and right value of a previous palindromic string
def check(s, bg, ed):
    if bg >= 0 and ed < len(s) and s[bg] == s[ed]:
        return check(s, bg - 1, ed + 1)
    else:
        return s[bg + 1: ed]

for i in range(len(s)):
    # This palindromic substring is with odd num
    longest_palin_string1 = check(s, i, i)

    # This palindromic substring is with even num, we just took the (i, i+1) because the condition of (i-1,i) is already considered in previous steps
    longest_palin_string2 = check(s, i, i + 1)

TBD

No.10 - Two string matching with special character

1
2
3
4
5
if j + 1 == '*':
    p[i][j] = p[i][j+2] or (current_match and p[i+1][j])
else:
    p[i][j] = current_match and p[i+1][j+1]

No.44 - Wildcard Matching

No.322 - Change Coin

1
2
3
4
for coin in coins:
    for j in range(coin, amount+1):
        d[j] = min(d[j], d[j - coin] + 1)
return d[amount]

Package Model

The problem can be described as a decision problem at step i

No.198 - House Robber

1
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

Posted on Edited on

恭喜宝贝儿拿到微软的奥佛！！！！！
牛逼！！！！！

Posted on Edited on In

The structure of computer is simple. For hardware, computer includes Memory, Controller, Processor and I/O devices. For software, the basic element is operating system.

CPU

Central Processing Unit (CPU) is the brain of the computer. It receives data, execute commands and process the data.

CPU can also be divided into following parts according to their functions.

Name Functions
Register Store the command code, data, and address data
Controller Fetch the command, data from memory to register, and execute the I/O devices
Arithmetic Logic Unit (ALU) Operate the data in register
Clock Count signal

All parts above are connected together via electricity’s signal.

The working pipeline of CPU is as follows.

  1. Fetch command. The Controller fetches the command from memory to registers, Program Counter stores the next address of command that needs to be executed.
  2. Decoding command. The Controller decodes the command according to existed rules, recognizes operation category and the methods.
  3. Executed command. The Controller handles the action of the command. e.g. Add numbers stored in two registers, compare two numbers.
  4. Fetch data. If the command needs to handle data, the Controller will fetch the data from the memory according to the address decoded from the command.
  5. Write Back. Write the answer of command to somewhere such as the registers in CPU.

Register

There are several kinds of register in CPU.

  • There is only one Program Counter, Flag Register, Accumulation Register, Instruction Register, and Stack Register in CPU.
  • There are several Base Register, Index Registers, and General Register in CPU.

Program Counter

It store the address of the unit in memory which stores the command that needs to be executed. It control the process of the program to be executed.

When the program is executed, the process is as follows.

  1. The controller fetches the command from memory according to the the address that is stored in Program Counter
  2. The controller analyzes and processes that command
  3. The address in Program Counter will increase by 1 or change to the address according to the conditional/loop command(JMP command in Assembly language), which points to the unit which stores the next command.
  4. If there is a function that needs to be executed, the next command will be stored in a Stack in memory, when the function is finished, the content of Program Counter will be set to the address in the top of Stack.

Flag Register

Flag Register stores the sign(+/-/0) of the Accumulation Register.

There is a compare action when conditional/loop function appears. When the compare function is executed, subtraction action will happen, and the answer is store in the Flag Register, then the Program Counter will be updated to corresponding address.

Base and Index Registers

A base register and several index registers can form an array. The array is stored continuously.

Memory

Memory has tight relationship with with CPU, CPU will fetch the command and data from disk to memory, and write back the command and data to disk.

There is several kinds of memory.

Name Functions
RAM Can be read and wrote. Data will lose when power off
ROM Can only be read. Data won’t lose when power off
Cache It has high read and write speed. CPU will handle the cache firstly. If there is no required data, CPU will fetch data in RAM

Memory has power, address signal, data signal, control signal.

I/O devices

Disk

The program stored in disk must be loaded to memory to be executed.

The disk has the following parts

Name Function
Disk Cache It stores the repeated content that memory requires to read from disk. It could accelerate the read speed of memory
Virtual Memory It can provide a virtual continuous memory for the program when the memory doesn’t enough space. The content in the real memory and the virtual memory will be swapped when required

Physcially, the disk is divided into different sector, which is the unit to do the read and write actions to disk. A disk will include 512 byte normally.

Operate System

Operate system could get over the difference of computer hardware except CPU.

The program just needs to call the API(Application Programming Interface) in operate system, then operate could handle the I/O devices.

Operate system includes:

  • Control program. Includes the hardware control and program execution control
  • Programming language processor. Compilation.
  • Application. e.g. txt Editor

Reference

[1] WeChat article