欧拉计划 发表于 2015-11-5 17:33:41

题目81：找出允许向下向右移动的情况下从左上角到右下角的最小路径和

Path sum: two ways

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.



Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.
题目：

在以下这个五乘五的矩阵中，在只允许向右和向下移动的情况下，从左上角到右下角的最小路径和是 2427，路径用红色标出。



包含一个 80×80 的矩阵，找出在只允许向右和向下移动的情况下，该矩阵中从左上角到右下角的最小路径和。

jerryxjr1220 发表于 2016-9-25 19:59:49

427337


master = [
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
]

for i in range(80):
        for j in range(80):
                if i==0 and j==0:
                        pass
                elif i == 0:
                        master += master
                elif j == 0:
                        master += master
                else:
                        if master < master:
                                master += master
                        else:
                                master += master
print (master)

芒果加黄桃 发表于 2017-2-24 18:35:33

# encoding:utf-8
# 计算最小路径
from time import time
nums = [
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
]

tris = []
def formatNums():
    for t in range(0, len(nums)):
      tt = t
      tmp = []
      while tt >= 0:
            tmp.append(nums)
            tt -= 1
      tris.append(tmp)
    for t in range(0, len(nums) - 1):
      tt = len(nums) - 1
      tmp = []
      while tt > t:
            tmp.append(nums)
            tt -= 1
      tris.append(tmp)   
def calTri(tri):
    for i in range(1, len(nums)):
      tri = tri + tri
      tri = tri + tri
      for j in range(1, i):
            if tri < tri:
                tri += tri
            else:
                tri += tri
def calNums():
    calTri(tris)
    tris_t = []      
    for each in tris:
      tris_t.append(each)
    calTri(tris_t)
    print(min(tris_t))   
def euler081(N=100):
    formatNums()
    calNums()
if __name__ == '__main__':
    start = time()
    euler081()
    print('cost %.6f sec' % (time() - start))

427337
cost 0.008001 sec

najin 发表于 2017-10-8 01:20:38

用的matlab
结果是
      427337

时间已过 0.004120 秒。
>>

永恒的蓝色梦想 发表于 2020-4-29 16:54:33

本帖最后由 永恒的蓝色梦想 于 2021-2-11 17:00 编辑

C++ 9ms#include<iostream>
#include<fstream>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    istream file("p081_matrix.txt");
    unsigned char i, j;
    unsigned int arr;


    for (i = 0; i < 80; i++) {
      for (j = 0; j < 80; j++) {
            file >> arr;
            file.get();

            if (i) {
                if (j) {
                  if (arr < arr) {
                        arr += arr;
                  }
                  else {
                        arr += arr;
                  }
                }
                else {
                  arr += arr;
                }
            }
            else {
                arr += arr;
            }
      }
    }


    cout << arr << endl;
    return 0;
}

debuggerzh 发表于 2020-8-27 20:34:03

427337

Process returned 0 (0x0)   execution time : 0.037 s
Press any key to continue.
dp题，确实应当用递推计算，递归深度太大
#include<cstdio>
#include<cmath>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int R = 80;
int a;

void parse(string & s){
for (int i = 0;i < s.length();i++)
    if (s == ',')s = ' ';
}

int main(){
freopen("i.in","r",stdin);

for (int i = 1;i <= R;i++){
    string s;
    getline(cin,s);
    parse(s);
    stringstream ss(s);
    for (int j = 1;j <= R;j++) ss >> a;
}

for (int i = 2;i <= R;i++)a += a;
for (int j = 2;j <= R;j++)a += a;

for (int i = 2;i <= R;i++)
    for (int j = 2;j <= R;j++)
      a += min(a,a);

cout << a << endl;
return 0;
}

guosl 发表于 2022-1-14 20:53:53

典型的动态规划。
令f为从左上角按题目要求到(i,j)的最小和，则转移方程为：f=min(f,f)+a 当（i>0,j>0）或f=f+a或f=f+a。
页: [1]
查看完整版本: 题目81：找出允许向下向右移动的情况下从左上角到右下角的最小路径和