一起刷算法_动态规划01

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

type NumArray struct {
}
var sum *[]int
func Constructor(nums []int) NumArray {
	var obj NumArray
	for k, v := range nums {
		if k > 0 {
			nums[k] = nums[k-1] + v
		}
	}
	sum = &nums
	return obj
}

func (this *NumArray) SumRange(i int, j int) int {
	if i == 0 {
		return (*sum)[j]
	}
	return (*sum)[j] - (*sum)[i-1]
}


func Test(){
	arr := []int{1,2,3,4}
	obj := Constructor(arr)
	res := obj.SumRange(0,3)
	fmt.Println(res)
}

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

// f(n) = f(n-1) +  f(n-2) (n>=3)
// f(1) = 1
// f(2) = 2
// 方法一、递归
func climbStairs1(n int)int{
	if n < 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	return climbStairs1(n-1) + climbStairs1(n-2)
}

//方法二、动归
func climbStairs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	res,a,b := 0,1 ,2

	for i:=3;i<=n;i++{
		res = a + b
		a = b
		b = res
	}
	return res
}

func Test1(){
	fmt.Println(climbStairs1(10))
}
func Test2(){
	fmt.Println(climbStairs(100))
}

221. Maximal Square
Medium

1165

29

Favorite

Share
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

// 方法二
func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    cols := 0
    if rows>0{
    	cols = len(matrix[0])
	}else{
		cols = 0
	}
	dp := make([][]int,rows+1)
	for i:=0;i < len(dp);i++{
		dp[i] = make([]int,cols+1)
	}
	maxlen := 0
	for x:=1;x <= rows; x++{
		for y:=1;y <= cols;y++{
			if matrix[x-1][y-1] == '1'{
				tmp := min(min(dp[x-1][y],dp[x][y-1]),dp[x-1][y-1])+1
				dp[x][y]=tmp
				maxlen = max(maxlen,tmp)
			}
		}
	}
	return maxlen * maxlen
}

// 方法三
func maximalSquare2(matrix [][]byte) int {
	rows := len(matrix)
	cols := 0
	if rows>0{
		cols = len(matrix[0])
	}else{
		cols = 0
	}
	dp := make([]int,cols +1)
	maxlen,prev := 0,0
	for x:=1;x <= rows; x++{
		for y:=1;y <= cols;y++{
			tmp := dp[y] //当前值当下一次的prev
			if matrix[x-1][y-1] == '1'{
				dp[y] = min(min(dp[y],dp[y-1]),prev) + 1 //分别对应上，左，左上
				maxlen = max(dp[y],maxlen)
			}else{
				dp[y] = 0
			}
			prev = tmp
		}
	}
	return maxlen * maxlen
}
func Test1(){
	t1 :=[][]byte{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}
	t2 :=[][]byte{}
	fmt.Println(maximalSquare(t2))
	fmt.Println(maximalSquare2(t1))
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}