题目一

image-20230924184045131

单元测试

package testing

import (
    "github.com/go-playground/assert/v2"
    "go_learn/alt/dp/q1/a1"
    "go_learn/alt/dp/q1/a2"
    "go_learn/alt/dp/q1/a3"
    "testing"
)

var N = 7
var M = 2
var K = 4
var P = 4
var Want = 4

func Test_A1(t *testing.T) {
    var r Runner = new(a1.C)
    ans := r.Run(N, M, K, P)
    assert.Equal(t, Want, ans)
}
func Test_A2(t *testing.T) {
    var r Runner = a2.NewRunner(N, K)
    ans := r.Run(N, M, K, P)
    assert.Equal(t, Want, ans)
}
func Test_A3(t *testing.T) {
    var r Runner = new(a3.C)
    ans := r.Run(N, M, K, P)
    assert.Equal(t, Want, ans)
}

type Runner interface {
    Run(N, M, K, P int) int
}
=== RUN   Test_A1
--- PASS: Test_A1 (0.00s)
=== RUN   Test_A2
--- PASS: Test_A2 (0.00s)
=== RUN   Test_A3
--- PASS: Test_A3 (0.00s)
PASS

题解一：暴力递归

package a1

type C struct {
}

//Run
/*
    N 长度
    M 起始位置
    K 走多少
    P 目标终点

*/
func (c *C) Run(len, cur, size, target int) int {
    if size == 0 {
        if cur == target {
            return 1
        }
        return 0
    }
    count := 0
    if cur != 1 {
        count += c.Run(len, cur-1, size-1, target)
    }
    if cur != len {
        count += c.Run(len, cur+1, size-1, target)
    }
    return count
}

题解二：记忆化搜索

package a2

type C struct {
    dp [][]int
}

//Run
/*
    N 长度
    M 起始位置
    K 走多少
    P 目标终点

*/
func (c *C) Run(len, cur, size, target int) int {
    if c.dp[cur][size] != -1 {
        return c.dp[cur][size]
    }
    if size == 0 {
        if cur == target {
            return 1
        }
        return 0
    }
    count := 0
    if cur != 1 {
        count += c.Run(len, cur-1, size-1, target)
    }
    if cur != len {
        count += c.Run(len, cur+1, size-1, target)
    }
    c.dp[cur][size] = count
    return count
}

func NewRunner(N, K int) *C {
    c := new(C)
    for i := 0; i < N; i++ {
        var l []int
        for j := 0; j <= K; j++ {
            l = append(l, -1)
        }
        c.dp = append(c.dp, l)
    }
    return c
}

题解三：表依赖

通过 baseKey 然后找出常式计算出整张表

package a3

type C struct {
}

//Run
/*
   N 长度
   M 起始位置
   K 走多少
   P 目标终点

*/
func (c *C) Run(len, cur, size, target int) int {
   var dp [][]int
   for i := 0; i <= len; i++ {
      var l []int
      for j := 0; j <= size; j++ {
         l = append(l, 0)
      }
      dp = append(dp, l)
   }
   dp[target][0] = 1
   for i := 1; i <= size; i++ {
      dp[1][i] = dp[2][i-1]
      for j := 2; j < len; j++ {
         dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]
      }
      dp[len][i] = dp[len-1][i-1]
   }
   return dp[cur][size]
}

image-20230924203935606

题目二

image-20230924204527908

单元测试

package testing

import (
    "github.com/go-playground/assert/v2"
    "go_learn/alt/dp/q2/a1"
    "go_learn/alt/dp/q2/a2"
    "go_learn/alt/dp/q2/a3"
    "testing"
)

var arr = []int{5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7}
var want = 32

func Test_A(t *testing.T) {
    var r Runner = new(a1.C)
    ans := r.Run(arr)
    assert.Equal(t, want, ans)
}

func Test_B(t *testing.T) {
    var r Runner = a2.NewRunner(arr)
    ans := r.Run(arr)
    assert.Equal(t, want, ans)
}

func Test_C(t *testing.T) {
    var r Runner = a3.NewRunner(arr)
    ans := r.Run(arr)
    assert.Equal(t, want, ans)
}

type Runner interface {
    Run(arr []int) int
}
=== RUN   Test_A
--- PASS: Test_A (0.00s)
=== RUN   Test_B
--- PASS: Test_B (0.00s)
=== RUN   Test_C
--- PASS: Test_C (0.00s)
PASS

题解一：暴力破解

package a1

type C struct {
}

func (c *C) Run(arr []int) int {
    L, R := 0, len(arr)-1
    return max(f(arr, L, R), g(arr, L, R))
}

// f 先手，获取最好的值
func f(arr []int, L, R int) int {
    if L == R {
        return arr[L]
    }
    p1 := arr[L] + g(arr, L+1, R)
    p2 := arr[R] + g(arr, L, R-1)
    return max(p1, p2)
}

// g 后手，尝试获取最好的值，但是要考虑对手不会让我们获取最好的结果
func g(arr []int, L, R int) int {
    if L == R {
        return 0
    }
    p1 := f(arr, L+1, R)
    p2 := f(arr, L, R-1)
    return min(p1, p2)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    return -max(-a, -b)
}

题解二：记忆化搜索

package a2

type C struct {
    fdp [][]int
    gdp [][]int
}

func (c *C) Run(arr []int) int {
    L, R := 0, len(arr)-1
    return max(c.f(arr, L, R), c.g(arr, L, R))
}
func NewRunner(arr []int) *C {
    c := new(C)
    l := len(arr)
    for i := 0; i < l; i++ {
        var fa, ga []int
        for j := 0; j < l; j++ {
            fa = append(fa, -1)
            ga = append(ga, -1)
        }
        c.fdp = append(c.fdp, fa)
        c.gdp = append(c.gdp, ga)
    }
    return c
}

// f 先手，获取最好的值
func (c *C) f(arr []int, L, R int) int {
    if L == R {
        return arr[L]
    }
    if c.fdp[L][R] != -1 {
        return c.fdp[L][R]
    }
    p1 := arr[L] + c.g(arr, L+1, R)
    p2 := arr[R] + c.g(arr, L, R-1)
    ans := max(p1, p2)
    c.fdp[L][R] = ans
    return ans
}

// g 后手，尝试获取最好的值，但是要考虑对手不会让我们获取最好的结果
func (c *C) g(arr []int, L, R int) int {
    if L == R {
        return 0
    }
    if c.gdp[L][R] != -1 {
        return c.gdp[L][R]
    }
    p1 := c.f(arr, L+1, R)
    p2 := c.f(arr, L, R-1)
    ans := min(p1, p2)
    c.gdp[L][R] = ans
    return min(p1, p2)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    return -max(-a, -b)
}

题解三：表依赖

package a3

type C struct {
    fdp [][]int
    gdp [][]int
    len int
}

func (c *C) Run(arr []int) int {
    return max(c.fdp[0][c.len-1], c.gdp[0][c.len-1])
}
func NewRunner(arr []int) *C {
    c := new(C)
    l := len(arr)
    c.len = l
    for i := 0; i < l; i++ {
        var fa, ga []int
        for j := 0; j < l; j++ {
            fa = append(fa, 0)
            ga = append(ga, 0)
        }
        c.fdp = append(c.fdp, fa)
        c.gdp = append(c.gdp, ga)
        c.fdp[i][i] = arr[i]
        c.gdp[i][i] = 0
    }
    for i := 1; i < l; i++ {
        L, R := 0, i
        for R < l {
            c.fdp[L][R] = max(arr[L]+c.gdp[L+1][R], arr[R]+c.gdp[L][R-1])
            c.gdp[L][R] = min(c.fdp[L+1][R], c.fdp[L][R-1])
            L++
            R++
        }
    }
    return c
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    return -max(-a, -b)
}

心得

通过暴力破解找出常式，通过原始数据递归算出依赖表，然后直接获取数据。

文章目录