金泰元アリババと40人の泥棒

3547 ワード
テキストリンク

ポリシー


  • 実施ですか?と思いましたが、左上を見て、最小値を
    検索し、前の値の結果から結果をエクスポートします.
    ダイナミックプログラミングと考えられます.

  • 最初は実装で、アクセス+問題を理解していません.
    解けなかった.

    • そっと



    ソースコード

    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(void)
{
	int n;
	cin >> n;

	vector<vector<int>>v(n, vector<int>(n, 0));
	vector<vector<int>>dp(n, vector<int>(n, 0));
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> v[i][j];
		}
	}

	int result = v[0][0];
	//오른쪽으로만, 아래로만 

	for (int i = 1; i < n; i++)
	{
		v[0][i] += v[0][i - 1];
		v[i][0] += v[i - 1][0];
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < n; j++)
		{
			v[i][j] += min(v[i - 1][j], v[i][j - 1]);
		}
	}

	cout << v[n - 1][n -1];


}

    2番目のソースコード

    #include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;



int main()
{
	int n;
	cin >> n;

	vector<vector<int>>v(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i < n + 1; i++)
	{
		for (int j = 1; j < n + 1; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 1; i < n + 1; i++)
	{
		for (int j = 1; j < n + 1; j++)
		{
			if (v[i][j - 1] == 0)
			{
				v[i][j] += v[i - 1][j];
			}
			else if (v[i - 1][j] == 0)
			{
				v[i][j] += v[i][j - 1];
			}
			else 
			v[i][j] = v[i][j] + min(v[i - 1][j], v[i][j - 1]);
			
		}
	}

	cout << v[n][n];

}
    CentOS 7アリクラウドyumソースの構成
    コンストラクタ