矩阵的最小路径和

C++ 解法, 执行用时: 9ms, 内存消耗: 1420KB, 提交时间: 2022-05-08

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline void read(T& f) {
    f = 0;
    T fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            fu = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + (c & 15);
        c = getchar();
    }
    f *= fu;
}
template <typename T>
void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t) {
    print(x);
    putchar(t);
}
int n, m, a[505][505];
void solve() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            read(a[i][j]);
    }
    for (int j = 1; j <= m; ++j)
        a[1][j] += a[1][j - 1];
    for (int i = 1; i <= n; ++i)
        a[i][1] += a[i - 1][1];
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= m; ++j) {
            a[i][j] += min(a[i - 1][j], a[i][j - 1]);
        }
    }
    print(a[n][m]);
}

int main() {
#ifdef AC
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    clock_t program_start_clock = clock();
    solve();
    fprintf(stderr, "\nTotal Time: %lf ms",
            double(clock() - program_start_clock) / (CLOCKS_PER_SEC / 1000));
    return 0;
}

C++ 解法, 执行用时: 9ms, 内存消耗: 1420KB, 提交时间: 2022-03-05

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f)
{
    f=0;T fu=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
    while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
    f*=fu;
}
template <typename T>
void print(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+48);
    else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t)
{
    print(x);putchar(t);
}
int n,m,a[505][505];
void solve()
{
    read(n),read(m);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        read(a[i][j]);
    }
    for(int j=1;j<=m;++j)
    a[1][j]+=a[1][j-1];
    for(int i=1;i<=n;++i)
    a[i][1]+=a[i-1][1];
    for(int i=2;i<=n;++i)
    {
        for(int j=2;j<=m;++j)
        {
            a[i][j]+=min(a[i-1][j],a[i][j-1]);
        }
    }
    print(a[n][m]);
}
int main()
{
    #ifdef AC
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    clock_t program_start_clock=clock();
    solve();
    fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
    return 0;
}

C++ 解法, 执行用时: 9ms, 内存消耗: 2332KB, 提交时间: 2022-08-05

#include<cstdio>
#include<algorithm>

using namespace std;

template <typename T>
inline void read(T& f) {
	f = 0;
	T fu = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') {
			fu = -1;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		f = (f << 3) + (f << 1) + (c & 15);
		c = getchar();
	}
	f *= fu;
}
template <typename T>
void print(T x) {
	if (x < 0) putchar('-'), x = -x;
	if (x < 10) putchar(x + 48);
	else print(x / 10), putchar(x % 10 + 48);
}

int map[505][505];
int dp[505][505];
int n, m;

int main(){
	read(n);read(m);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			read(map[i][j]);
		}
	}
	for(int i = 1;i <= n;i++)dp[i][1] = map[i][1] + dp[i-1][1];
	for(int j = 1;j <= m;j++)dp[1][j] = map[1][j] + dp[1][j-1];
	for(int i = 2;i <= n;i++){
		for(int j = 2;j <= m;j++){
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + map[i][j];
		}
	}
	print(dp[n][m]);
	
	return 0;
}

Go 解法, 执行用时: 13ms, 内存消耗: 4804KB, 提交时间: 2022-06-28

package main

import (
    "fmt"
    "bufio"
    "os"
)

func getMinPath(n, m int, matrix [502][502]int) int {
    // 初始化 
    dp = matrix[0]
    
    for j:=1;j<m;j++ {
        // 也可以写成  dp[j] = dp[j-1]+matrix[0][j]
        dp[j] += dp[j-1]
    }
    
    for i:=1;i<n;i++ {
        dp[0] += matrix[i][0]
        for j:=1;j<m;j++ {
            dp[j] = myMin(dp[j],dp[j-1])+matrix[i][j]
        }
    }
    return dp[m-1]
}

func myMin(x, y int) int {
    if x < y {
        return x
    }
    return y
}

var in = bufio.NewReader(os.Stdin)

func read() (x int) {
    c, _ := in.ReadByte()
    for ;c >= '0';c, _ = in.ReadByte() {
        x = x * 10 + int(c)&15
    }
    return
}

var matrix [502][502]int
var dp [502]int

func main() {
    n := read()
    m := read()
    
    for i:=0;i<n;i++ {
        for j:=0;j<m;j++ {
            matrix[i][j] = read()
        }
    }
    fmt.Printf("%d\n", getMinPath(n, m, matrix))
}

Go 解法, 执行用时: 19ms, 内存消耗: 7192KB, 提交时间: 2022-03-16

package main
import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
)
func main() {
    input := bufio.NewReader(os.Stdin)
    s, _ := input.ReadString('\n')
    s = strings.ReplaceAll(s, "\n", "")
    strs := strings.Split(s, " ")
    var n, m int
    n, _ = strconv.Atoi(strs[0])
    m, _ = strconv.Atoi(strs[1])
    var nums = make([][]int, n)
    for i := 0; i < n; i++ {
        s, _ = input.ReadString('\n')
        s = strings.ReplaceAll(s, "\n", "")
        strs = strings.Split(s, " ")
        nums[i] = make([]int, m)
        for j := 0; j < m; j++ {
            nums[i][j], _ = strconv.Atoi(strs[j])
        }
    }
//     fmt.Println(nums)
    var dp = nums[0]
    for i := 1; i < m; i++ {
        dp[i] += dp[i-1]
    }
//     fmt.Println(dp)
    for i := 1; i < n; i++ {
        dp[0] += nums[i][0]
        for j := 1; j < m; j++ {
            dp[j] = min(dp[j], dp[j-1]) + nums[i][j]
        }
    }
    fmt.Println(dp[m-1])
}
func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

详情